Algoritma untuk meminimalkan Moore automata

Algoritma Brzozowski dapat diperluas ke Moore automata tetapi kompleksitas waktunya eksponensial secara umum. Apakah ada algoritma lain untuk meminimalkan Moore automata? Berapa kali menjalankan algoritma ini jika ada?

Algoritma minimalisasi DFA asli sebenarnya dirancang untuk Moore Machines , dipandu oleh perilaku yang tampaknya lebih dapat diamati. Tetapi algoritma yang disajikan di sini adalah rekonstruksi dari minimalisasi DFA, karena saya menemukan bukti historis setelah fakta.

Setelah Wikipedia (dengan beberapa perubahan notasi):

Sebuah mesin Moore dapat didefinisikan sebagai 6-tuple yang terdiri dari:$(Q, q_0, \Sigma, \Pi, \delta, \gamma)$

• satu set terbatas negara $Q$
• keadaan awal (juga disebut keadaan awal) yang merupakan elemen dari $q_0$$Q$
• satu set terbatas yang disebut alfabet input $\Sigma$
• himpunan terbatas yang disebut alfabet keluaran $\Lambda$
• fungsi transisi memetakan status dan alfabet input ke status berikutnya $\delta : Q \times \Sigma \rightarrow Q$
• fungsi output memetakan setiap negara bagian ke alfabet output $\gamma : Q \rightarrow \Pi$

Dari definisi ini, mesin Moore adalah transduser keadaan terbatas deterministik.

Saya tidak punya referensi untuk meminimalkan Moore automata. Namun tampaknya tidak terlalu sulit untuk membayangkan suatu algoritma, yang berasal dari algoritma yang digunakan untuk automata keadaan terbatas deterministik.

Gagasan dalam minimalisasi DFA didasarkan pada karakterisasi Myhill-Nerode dari bahasa reguler .

Mengingat bahasa , dan sepasang string x dan y , menentukan ekstensi membedakan menjadi string z sehingga tepat satu dari dua string x z dan y z milik L . Mendefinisikan hubungan R L pada string dengan aturan yang x R L y jika dan hanya jika tidak ada ekstensi yang membedakan untuk x dan y . Sangat mudah untuk menunjukkan bahwa R L adalah relasi ekivalen pada string, dan dengan demikian membagi himpunan semua string ke dalam kelas kesetaraan.$L$$x$$y$$z$$xz$$yz$$L$$R_L$$x R_L y$$x$$y$$R_L$

Teorema Myhill-Nerode menyatakan bahwa adalah reguler jika dan hanya jika R L memiliki jumlah kelas ekuivalen yang terbatas, dan terlebih lagi bahwa jumlah state dalam otomat terhingga deterministik terkecil (DFA) yang mengakui L sama dengan jumlah kelas ekivalen di R L .$L$$R_L$$L$$R_L$

Memang setiap negara dari DFA terkecil adalah seperti yang W q seperti yang didefinisikan di atas adalah salah satu kelas kesetaraan untuk hubungan R L .$q$$W_q$$R_L$

Untuk DFA non-minimal untuk bahasa reguler , mudah untuk menunjukkan bahwa setiap set W q mengandung string bahwa semua milik kelas setara sama sehubungan dengan R L .$L$$W_q$$R_L$

Oleh karena itu, minimalisasi DFA sebenarnya terdiri dari keadaan penggabungan (dianggap sebagai set string yang setara), setiap kali ditunjukkan bahwa dua negara yang berbeda mengandung string yang setara.

Ada dua algoritma yang cukup cepat untuk tujuan itu, algoritma Moore (1956) yang ada dalam waktu dan algoritma Hopcroft (1971) dalam waktu O ( n log n ) .$O(n^2)$$O(n\log n)$

Ekstensi untuk Moore automata paling dipahami dalam mendefinisikan ulang relasi ekivalen sebagai untuk transduser T . Relasi R L prihatin dengan apakah input masa depan akan mengarah ekuivalen untuk sebuah negara menerima. The R T relasi ekivalen dari Moore automata berkaitan dengan apakah input masa depan akan menghasilkan output yang sama.$R_T$$T$$R_L$$R_T$

Oleh karena itu, diberikan transduser , dan dua string x dan y , kita mendefinisikan ekstensi yang membedakan menjadi string z sedemikian rupa sehingga T ( x z ) = T ( x ) u dan T ( y z ) = T ( y ) v dengan u ≠ v , yaitu sedemikian sehingga perilaku keluaran transduser berbeda untuk z tergantung pada di mana ia mengikuti x atau y .$T$$x$$y$$z$$T(xz)=T(x)u$$T(yz)=T(y)v$$u\neq v$$z$$x$$y$

Sekali lagi, adalah relasi ekivalen, membagi semua string di Σ * ke dalam kelas kesetaraan. Dalam kasus mesin Moore, kelas-kelas ini akan kembali sesuai dengan keadaan transduser minimal.$R_T$$\Sigma^*$

Algoritma berikut meniru algoritma Moore untuk minimalisasi DFA.

Kami mendefinisikan partisi awal dari Q ke dalam kelas dari negara S e sebagai berikut:$\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Kemudian kami membagi kelas dalam sebagai berikut:$\mathcal P$

ulangi berturut-turut untuk setiap kelas status , sampai tidak ada perubahan yang berulang ∀ a ∈ Σ $S$
$\ \ $ $\forall a\in\Sigma,\;$
$\ \ \ \ $ Jika lalutidak melakukan hallain,membagi S menjadi himpunan bagian S i sedemikian rupa sehinggauntuk setiap subset S i , ada kelas S yang berbeda ′ ∈ P sedemikian rupa sehingga ∀ q ∈ S i$\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$$S'\in \mathcal P$ (himpunan bagian S i ganti S dalam P )$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $$S_i$$S$$\mathcal P$

Ketika tidak ada kelas yang tersisa yang perlu dipisah, kelas-kelas negara bagian yang tersisa akan membentuk keadaan mesin Moore minimal.

Dengan konstruksi, semua status di kelas memiliki output yang sama yang merupakan output untuk kelas.

Demikian pula, untuk setiap input , semua status di kelas pergi ke beberapa status di kelas lain yang sama, yang menentukan fungsi transisi untuk mesin Moore minimal.$a\in\Sigma$

$n=|Q|$$s=|\Sigma|$
$n$$O(sn^2)$

Saya tidak punya referensi untuk meminimalkan mesin Moore ini. Mungkin itu termasuk dalam makalahnya:

Moore, Edward F (1956). "Gedanken-eksperimen pada Mesin Sekuensial". Automata Studies , Annals of Mathematical Studies (Princeton, NJ: Princeton University Press) (34): 129-153.

Makalah ini adalah referensi utama yang memperkenalkan Moore Machines . Ini juga referensi untuk algoritma minimisasi DFA Moore . Dengan demikian seharusnya mengejutkan jika adaptasi algoritma untuk meminimalkan Moore Machines tidak setidaknya disarankan dalam makalah itu. Saya memang memeriksa makalah, dan versi algoritma minimisasi yang disajikan sebenarnya untuk mesin Moore, bukan untuk DFA. Makalah ini ditulis dengan baik, tetapi gaya waktu membuatnya agak sulit untuk dibaca. Sangat menarik untuk melihat bahwa banyak ide dari teori Myhill-Nerode dari Finite State Machines sudah dibuat sketsa dalam makalah ini.

$O(sn\log n)$

Versi algoritma Brzozowski menggunakan turunan dari ekspresi reguler diberikan dalam [2], Bab 12, Bagian 4, di mana ia dikreditkan ke [4]. Lihat [1] dan [3] untuk kasus yang lebih umum dari transduser berurutan (terminologi agak ketinggalan jaman dan istilah transduser berurutan mungkin lebih tepat saat ini).

[1] C. Choffrut, Meminimalkan transduser selanjutnya: survei, Theoret. Comp. Sci. 292 (2003), 131–143.

[2] S. Eilenberg, Automata, Bahasa dan Mesin, vol. A, Academic Press, 1974.

[3] J.-E. Pin, Tutorial tentang fungsi sekuensial . (Slide)

[4] GN Raney, Fungsi berurutan, JACM 5 (1958), 177–180.

Algoritma Brzozowski adalah titik awal yang buruk (jika Anda khawatir dengan runtime kasus terburuk asimptotik). Bahkan Wikipedia juga memberi tahu Anda:

Seperti yang diamati oleh Brzozowski (1963), membalikkan tepi-tepi DFA menghasilkan otomat terbatas hingga-non-deterministik (NFA) untuk pembalikan bahasa asli, dan mengonversi NFA ini menjadi DFA menggunakan konstruksi standar standar (hanya membangun keadaan yang dapat dijangkau dari DFA yang dikonversi) mengarah ke DFA minimal untuk bahasa terbalik yang sama. Mengulangi operasi pembalikan ini untuk kedua kalinya menghasilkan DFA minimal untuk bahasa asli. Kompleksitas terburuk dari algoritma Brzozowski adalah eksponensial, karena ada bahasa reguler yang DFA minimum pembalikannya secara eksponensial lebih besar daripada DFA minimal bahasa, [6] tetapi sering berkinerja lebih baik daripada yang disarankan oleh kasus terburuk ini.

Algoritma memiliki runtime kasus terburuk eksponensial bahkan pada DFA karena menghitung automaton untuk kebalikannya, yang mungkin harus besar secara eksponensial. Jadi masalah Anda tidak datang dari ekstensi ke transduser.

Cobalah untuk menyesuaikan algoritma minimalisasi DFA lainnya.