Menggeneralisasi algoritma minimisasi DFA Brzozowski untuk membatasi automata dengan berbagai kelas negara penerima?

9

Algoritma Brzozowski untuk mengubah DFA menjadi DFA minimum-state yang ekuivalen sangat sederhana: jika menunjukkan NFA yang dibentuk dengan membalik semua tepi dalam DFA D , menjadikan state awal yang lama sebagai negara penerima, dan menjadikan yang lama menerima negara mulai negara, dan jika P ( N ) menunjukkan hasil dari penerapan pembangunan bagian ke NFA N , maka P ( R ( P ( R ( D ) ) ) ) adalah minimum-negara DFA dengan bahasa yang sama dengan D .R(D)DP(N)N

P(R(P(R(D))))
D

Kita dapat menganggap DFA sebagai perangkat komputasi yang menerima string input dan kemudian menghasilkan 0 jika w berakhir dalam keadaan menolak dan 1 jika w berakhir dalam keadaan menerima. Generalisasi alami DFA menghubungkan setiap negara bagian dalam DFA dengan beberapa bilangan alami antara 0 dan k - 1 , inklusif.wwwk−1

Sepengetahuan saya, mungkin untuk meminimalkan kelas DFA yang dimodifikasi ini dengan menggunakan algoritma minimisasi berbasis-pembedaan, seperti yang kanonik oleh Hopcroft. Namun, saya tidak dapat melihat bagaimana mungkin untuk mengadaptasi algoritma minimisasi Brzozowski ke kelas automata baru ini karena langkah kunci (membalikkan automaton) tidak lagi memiliki interpretasi yang jelas dalam pengaturan umum ini.

Adakah generalisasi yang diketahui dari algoritma Brzozowski untuk meminimalkan automata semacam ini? Jika tidak, apakah ada alasan teoretis mengapa kita berharap algoritma yang dimodifikasi seperti itu tidak ada?

automata-theory minimization templatetypedef
sumber
"generalisasi" tampaknya tidak didefinisikan dengan jelas. apa itu ? apakah itu hanya berbicara tentang mengaitkan setiap negara dalam DFA dengan nilai integer terbatas? lalu apa? apa contohnya? siapa yang bekerja dengan ini? dllk
vzn
{0,1,2,3,...,k−1}
ok, itu tidak dikomunikasikan dalam posting sama sekali, "DFA menampilkan # yang terkait dengan keadaan string berakhir", menyarankan Anda memperbaikinya. juga, DFA secara teknis tidak memiliki "output". mungkin maksud Anda transduser FSM? memang ada beberapa teori parsial yang terkait dengan minimisasi transduser FSM yang tampaknya tidak ("belum"?) sepenuhnya terkait dengan meminimalkan DFA.
vzn

Jawaban:

7

Jawaban atas pertanyaan Anda adalah ya.

Lihat karya Bonchi, Bonsangue, Rutten dan Silva Algoritma Brzozowski (co) secara aljabar (versi konferensi yang lebih pendek) dan Dualitas Aljabar-Batubara di Algoritma Minimisasi Brzozowski (versi jurnal yang lebih panjang dengan lebih banyak generalisasi).

Mereka memberikan presentasi kategoris (ringan) dari algoritma Brzowzowski, dan menggunakannya untuk menurunkan versi-versi itu untuk kelas-kelas automata yang lebih umum, termasuk Moore automata (yang memberikan jawaban positif untuk pertanyaan Anda).

Neel Krishnaswami
sumber
6

Hanya untuk menambah jawaban Neel, dalam buku saya Sequences Otomatis dengan Jean-Paul Allouche kita membahas DFAO (automata terbatas deterministik dengan output), yang persis seperti yang Anda tanyakan (kaitkan output dengan masing-masing negara). Dan Teorema 4.3.3 menjelaskan cara membalikkan mesin seperti itu.

Jeffrey Shallit
sumber