Apa yang diketahui tentang kelas bahasa yang dikenali oleh automata terbatas yang memiliki keadaan awal dan penerima yang sama? Ini adalah bagian yang tepat dari bahasa biasa (karena setiap bahasa tersebut berisi string kosong), tetapi seberapa lemah itu? Apakah ada karakterisasi aljabar sederhana?
Ditto untuk bahasa yang dikenali oleh automata non-deterministik memiliki set yang sama dari negara awal dan penerima.
fl.formal-languages
automata-theory
algebra
regular-language
Noam Zeilberger
sumber
sumber
Jawaban:
Pertanyaan ini diselesaikan untuk automata deterministik dan untuk automata ambigu dalam buku [1]
[1] J. Berstel, D. Perrin, C, Reutenauer, Kode dan automata, Vol. 129 dari Ensiklopedia Matematika dan Penerapannya, Cambridge University Press, 2009.
Dalam kasus automata deterministik, karakterisasi diberikan dalam Proposisi 3.2.5. Ingat bahwa submonoid dari A * adalah kesatuan yang tepat jika, untuk semua u , v ∈ M , u , u v ∈ M menyiratkan v ∈ M .M A∗ u,v∈M u,uv∈M v∈M
Untuk automata yang tidak ambigu, karakterisasi mengikuti dari Teorema 4.2.2 dan dapat dinyatakan sebagai berikut:
Akhirnya, untuk automata nondeterministic, karakterisasi hanya yang adalah submonoid dari A * .L A∗
sumber
Automata terbatas di mana keadaan awal juga keadaan penerimaan unik memiliki bentuk , di mana r adalah beberapa ekspresi reguler. Namun, seperti J.-E. Pin menunjukkan di bawah ini, kebalikannya tidak benar: ada bahasa dalam bentuk r ∗ yang tidak diterima oleh DFA dengan negara penerima yang unik.r∗ r r∗
Secara intuitif, diberi urutan keadaan sedemikian rupa sehingga q 0 = q n baik n = 0 atau diagram keadaan yang mendasarinya harus memiliki siklus yang melibatkan q 0 . Kasus terakhir ditangkap secara aljabar oleh bintang Kleene.q0,…,qn q0=qn n=0 q0
sumber
Subclass penting dari keluarga ini adalah sub-kelas dari bahasa 0-reversibel. Suatu bahasa adalah 0-reversibel jika pembalikan DFA minimal untuk bahasa tersebut juga deterministik. Operasi pembalikan didefinisikan sebagai swapping keadaan awal dan akhir, dan membalikkan hubungan tepi DFA. Ini berarti bahwa bahasa 0-reversibel hanya dapat memiliki satu negara penerima. Pertanyaan Anda menambahkan batasan lebih lanjut bahwa keadaan ini harus menjadi keadaan awal. Batasan Anda tidak menentukan bahasa 0-reversibel karena DFA minimal untuk bahasa tersebut dapat memiliki keadaan awal dan akhir yang berbeda.
Kelas bahasa yang dapat dibalik menarik karena merupakan salah satu keluarga bahasa pertama dengan banyak string yang dapat dipelajari dari contoh-contoh positif saja. Makalah Angluin memberikan karakterisasi aljabar juga.
sumber
Anda dapat merujuk ke Semi-flower automata, sebagaimana makalah mereka tuliskan: "Otomat semi-bunga (SFA) adalah robot trim dengan keadaan awal yang unik yang sama dengan keadaan akhir yang unik di mana semua siklus akan melewati kondisi awal ". Merujuk pada "DOMPOSISI HOLONOMI AUTOMATA SEMI-BUNGA SIRKULAR" -Shubh Narayan Singh, KV Krishna.
sumber