Meminimalkan Automata yang menerima kata-

Apa pendekatan standar untuk meminimalkan Büchi-Automata (atau juga Müller-Automata)? Mentransfer teknik yang biasa dari kata-kata terbatas, yaitu menetapkan dua negara menjadi sama jika kata-kata "kehabisan" dari negara-negara yang diterima adalah sama, tidak akan berfungsi. Misalnya, pertimbangkan Büchi-Automoton yang menerima semua kata dengan jumlah tak terbatas dari a yang terdiri dari dua keadaan, keadaan awal dan akhir, dan keadaan akhir dimasukkan setiap kali a dibaca, dan keadaan awal dimasukkan setiap kali a simbol yang berbeda dibaca. Kedua negara dianggap sama dengan definisi di atas, tetapi runtuh mereka menghasilkan automata yang terdiri dari satu negara, dan dengan demikian menerima setiap kata.

Secara umum, bahasa $\omega$ regular mungkin tidak memiliki DBW minimal yang unik. Misalnya, bahasa "tak terhingga banyak dan jauh lebih banyak b" memiliki dua DBWs 3-state (dalam gambar menggantikan $\neg a$ oleh $b$ ):

Seperti yang Anda lihat, mereka tidak setara secara topologi.

Oleh karena itu, masalah minimisasi lebih sulit daripada kasus yang terbatas, dan pada kenyataannya, itu adalah NP-lengkap .

Pertanyaan ini menghasilkan banyak literatur di tahun 80-an, sebagian karena pendekatan yang buruk untuk masalah ini. Ini adalah cerita yang agak panjang yang akan saya rangkum dalam jawaban ini.

1. Kasus kata-kata yang terbatas

Seseorang dapat menemukan dua definisi DFA minimal dalam literatur. Yang pertama adalah untuk menentukan DFA minimal bahasa biasa sebagai DFA lengkap dengan jumlah minimum negara yang menerima bahasa. Yang kedua lebih panjang untuk didefinisikan tetapi secara matematis lebih menarik dari yang pertama dan itu memberikan sifat yang lebih kuat.

Mari kita ingat bahwa sebuah DFA adalah diakses jika untuk semua q ∈ Q , ada sebuah kata u ∈ A * seperti yang saya ⋅ u = q . Hal ini lengkap jika q ⋅ sebuah didefinisikan untuk semua q ∈ Q dan sebuah ∈ A .$(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Misalkan dan A 2 = ( Q 2 , A , ⋅ , i 2 , F 2 ) menjadi dua DFA yang lengkap dan dapat diakses. Morfisme dari A 1 ke A 2 adalah fungsi φ : Q 1 → Q 2 sedemikian rupa${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. ,$\varphi(i_1) = i_2$
2. ,$\varphi^{-1}(F_2) = F_1$
3. untuk semua dan a ∈ A , φ ( q ) ⋅ a = φ ( q ⋅ a ) .$q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

Satu dapat menunjukkan bahwa kondisi ini menyiratkan bahwa harus bersifat surjektif (dan dengan demikian | Q 2 | ⩽ | Q 1 | ). Lebih jauh lagi, ada paling banyak satu morfisme dari A 1 ke A 2 dan jika morfisme ini ada, maka A 1 dan A 2 mengenali bahasa yang sama. Sekarang, orang dapat menunjukkan bahwa untuk setiap bahasa L , ada DFA A L yang dapat diakses dan unik yang dapat diterima L dan sedemikian rupa sehingga, untuk setiap akses yang lengkap DFA A menerima $\varphi$$|Q_2| \leqslant |Q_1|$${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$$\cal A$$L$, Ada morphism dari ke A L . Robot ini disebut DFA minimal dari L . Perhatikan lagi bahwa karena jumlah negara di A L lebih kecil dari jumlah negara di A , A L juga minimal dalam arti pertama.$\cal A$${\cal A}_L$$L$${\cal A}_L$$\cal A$${\cal A}_L$

Perlu disebutkan bahwa ada juga definisi aljabar yang cocok untuk DFA tidak lengkap . Lihat [Eilenberg, Automata, Bahasa dan Mesin , vol. A, Academic Press, 1974] untuk lebih jelasnya.

2. Kembali ke kata-kata yang tak terbatas

Memperluas definisi pertama tidak berhasil, seperti yang ditunjukkan oleh Shaull dalam jawabannya. Dan sayangnya seseorang juga dapat menunjukkan bahwa properti universal dari definisi kedua tidak meluas ke kata-kata yang tak terbatas, kecuali dalam beberapa kasus tertentu.

Apakah ini akhir dari cerita? Tunggu sebentar, ada objek minimal lain yang menerima bahasa biasa ...

3. Pendekatan sintaksis

Mari kita kembali lagi ke kata yang terbatas. Ingat bahwa bahasa dari A * adalah diakui oleh monoid M jika ada surjective monoid morphism f : A * → M dan subset P dari M sehingga f - 1 ( P ) = L . Sekali lagi, ada sebuah monoid M ( L ) , yang disebut monoid sintaksis dari L , yang mengakui L dan merupakan hasil bagi semua monoids mengakui $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$$L$$L$$L$. Monoid sintaksis ini dapat didefinisikan secara langsung sebagai hasil bagi dari oleh kesesuaian sintaksis ~ L dari L , didefinisikan sebagai berikut: u ~ L v  jika dan hanya jika, untuk semua  x , y ∈ A * ,  x u y ∈ $A^*$ $\sim_L$$L$ Kabar baiknya adalah bahwa kali ini, pendekatan ini telah diperluas ke kata-kata yang tak terbatas, tetapi butuh waktu lama untuk menemukan gagasan yang sesuai. Pertama, gagasan yang cocok dari kongruensi sintaksis ditemukan oleh A. Arnold (Kongruensi sintaksis untuk bahasaω-bahasarasional,Theoret. Compi. Sci.39, 2-3 (1985), 333-335). Memperluas mono sintaksis ke pengaturan kata-kata tak terbatas membutuhkan jenis aljabar yang lebih canggih, yang sekarang disebutaljabar Wilkeuntuk menghormati T. Wilke, yang merupakan orang pertama yang mendefinisikannya (T. Wilke, Teori aljabar untuk bahasa reguler terbatas dan tak terbatas kata-kata,Int. J. Alg. Comput.3

4. Kesimpulan

Dengan demikian ada gagasan suara matematis dari objek minimal yang menerima bahasa- , tetapi tidak bergantung pada automata. Ini sebenarnya fakta yang agak umum: automata adalah alat algoritmik yang sangat kuat, tetapi mereka tidak selalu cukup untuk menangani pertanyaan matematika pada bahasa.$\omega$