Algoritma untuk mengecilkan DFA dengan memperkenalkan nondeterminisme?

Ini agak terkait dengan pertanyaan lain yang saya ajukan , tetapi saya merasa itu cukup berbeda untuk menjamin pertanyaannya sendiri.

Saya sedang melakukan penelitian di mana saya mencoba untuk menemukan struktur pelengkap kelas tertentu dari bahasa yang terbatas. Sangat mudah bagi saya untuk mendapatkan DFA minimal yang menerima bahasa-bahasa ini, tetapi saya ingin memeriksa seperti apa struktur NFA yang menerima bahasa ini, terutama bagaimana nondeterminisme membantu dengan automata ukuran negara (DFA secara eksponensial besar).

Masalahnya adalah, teknik reduksi NFA utama menggunakan persamaan, yang tidak akan menghasilkan reduksi jika saya mulai dengan DFA minimal (karena pada dasarnya menggunakan teknik yang sama). Jika saya mulai dengan DFA non-minimal, itu hanya memuntahkan DFA minimal.

Yang saya ingin tahu adalah, apakah ada algoritma yang dapat dimulai dengan DFA, dan mengecilkannya menjadi NFA yang lebih kecil dengan memperkenalkan nondeterminisme? Apakah ada "teknik standar" untuk melakukan ini?

Saya telah menemukan pengurangan preorder , yang terlihat menjanjikan tetapi sulit untuk diterapkan. Saya terbuka untuk banyak saran.

Untuk heuristik efisien saya sarankan melihat literatur CAD pada masalah pengkodean negara (menetapkan pengidentifikasi biner ke keadaan DFA untuk meminimalkan jumlah logika untuk fungsi transisi negara.) Devadas dan Newton, "Dekomposisi dan faktorisasi berurutan hingga berurutan mesin negara, " IEEE TCAD , 8 (11): 1206-1217, 1989 menunjukkan bahwa ada hubungan erat antara pengodean negara dan dekomposisi mesin negara.

Jika untuk DFA dengan status Anda menetapkan pengenal status bit unik untuk setiap status ( ), maka pada dasarnya Anda telah mendekomposisi DFA ke dalam jaringan berinteraksi dengan dua mesin state. Setara: Anda telah menetapkan himpunan dengan elemen , dan menetapkan subset unik untuk setiap negara bagian dalam DFA asli Anda. Ini juga yang dilakukan oleh algoritma konstruksi powersin Rabin-Scott . Jadi dengan melakukan pengkodean keadaan pada DFA kami mencoba merekayasa balik himpunan yang dimulai dengan algoritma konstruksi powerset.$N$$M$$\lg_2N < M\leq N$$M$$S$$M$$S$

Dalam masalah penyandian keadaan tradisional semua penyandian adalah legal, dan ada beberapa fungsi objektif (terkait dengan jumlah logika dalam fungsi transisi negara) yang Anda coba untuk meminimalkan. Untuk menghasilkan NFA, Anda perlu menyelesaikan versi terbatas dari masalah pengkondisian tempat:

pengodean pengidentifikasi bit ke status DFA mewakili NFA iff untuk setiap simbol dalam alfabet fungsi transisi untuk setiap bit adalah disjungsi bit yang sederhana. (Tidak ada konjungsi atau negasi yang diizinkan.)$M$

Jadi Anda bisa menghitung semua penyandian bit untuk semua , dan memeriksa apakah masing-masing memenuhi kendala. (Perhatikan bahwa untuk , pengkodean "satu-panas" yang sepele selalu memenuhi batasan, dan memberi Anda DFA.) Namun, enumerasinya sangat besar, (buku teks Di Micheli memberikannya sebagai sesuatu seperti .) Alasan saya menyarankan literatur CAD adalah bahwa ada teknik untuk melakukan pencarian ini secara implisit daripada enumerasi (misalnya, dengan menggunakan BDD, lihat Lin, Touati dan Newton, "Jangan pedulikan minimalisasi jaringan logika sekuensial multi-level," Int'l Conf Comp-Aided Dsgn ICCAD-90: 414-417, 1990 .$M$$\lg_2N < M\leq N$$M=N$$\frac{2^M !}{(2^M - N)!M!}$

Contoh

Ambil DFA berikut, (dengan penyandian status yang saya dapatkan dengan cara curang (saya membuat DFA dari NFA menggunakan Rabin-Scott, dan penyandian mewakili subset yang dipilih oleh Rabin-Scott.))

Jika kita memanggil bit dalam penugasan keadaan ABCD, maka ketika simbol input adalah 1, fungsi transisi adalah A = A, B = A, C = B, D = C. Ketika simbol input adalah 0, fungsi transisi adalah A = A, C = B, D = C. Ini adalah fungsi transisi disjungtif murni tanpa konjungsi atau negasi, sehingga pengkodean keadaan ini memberi kita NFA. Status di NFA sesuai satu-ke-satu dengan bit dalam penyandian, dan fungsi transisi seperti yang diberikan:

Formulasi sebagai masalah kepuasan boolean

Deskripsi informal di atas mengarah langsung ke pengkodean sebagai masalah kepuasan boolean. Ada satu set variabel yang menggambarkan transisi dalam NFA, dan satu set variabel untuk pengkodean status DFA yang akan diturunkan dari Rabin-Scott untuk NFA yang dipilih. Transisi DFA spesifik yang Anda coba dekomposisi digunakan untuk menempatkan kendala pada transisi NFA.

Misalkan kita diberi DFA dengan menyatakan untuk bahasa dengan simbol, dan kami ingin mendapatkan sebuah negara NFA, dengan . Kami akan menggunakan variabel untuk mewakili transisi yang mungkin dalam NFA. akan benar jika jika ada transisi dalam NFA dari status NFA ke status NFA pada simbol . Dalam contoh NFA di atas, alfabetnya berukuran 2 dan ada 4 status NFA, jadi ada variabel dan , dan$N$$S$$M$$\lg_2N<M\leq N$$y_{sft}$$y_{sft}$$f$ $t$ $s$$SM^2=32$ $y$$y_{0AA}, y_{1AA}$$y_{1AB}$semuanya benar sedangkan salah.$y_{1DA}$

Kami akan menggunakan variabel untuk menunjukkan apakah algoritma Rabin-Scott harus menyertakan status NFA di set status yang memberi label status DFA . Dalam contoh di atas kita memiliki status DFA dan status NFA sehingga ada 32 variabel. Pada contoh di atas, anggaplah keadaan paling bawah (yang berlabel "1011") adalah keadaan , maka , , dan benar sedangkan salah.$x_{dn}$$n$$d$$N=8$$M=4$$x$$k$$x_{kA}$$x_{kC}$$x_{kD}$$x_{kB}$

Sekarang kendala. Pertama-tama, Rabin-Scott harus menemukan pengkodean yang berbeda untuk setiap status DFA, jadi untuk status DFA, dan semua status NFA : $i < j$$\{A,B,\cdots, D\}$

$$(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).$$

Selanjutnya harus menjadi kasus bahwa jika Rabin-Scott menemukan transisi dari negara DFA ke negara DFA pada simbol maka untuk setiap negara NFA termasuk dalam pengkodean harus ada negara NFA dari pengkodean negara DFA sedemikian rupa sehingga NFA asli memiliki transisi dari ke . Pada contoh di atas, pada simbol "1" ada transisi DFA dari negara DFA "1000" ke negara DFA "1100" sehingga harus ada transisi NFA dari negara NFA A ke negara NFA A dan B dan tidak ada transisi NFA dari NFA negara A ke salah satu negara NFA C atau D. Jadi untuk masing - masing$i$$j$$s$$k$$j$$l$$j$$l$$k$$o(SN^2)$ tepi dalam DFA kita memiliki batasan:

$$\begin{eqnarray*} x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\ x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\ & & \cdots \\ x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}. \end{eqnarray*}$$

Akhirnya kita harus berurusan dengan permulaan dan menerima negara. Status awal DFA dikodekan dengan penyatuan status awal NFA, sehingga status awal DFA lebih baik tidak dikodekan dengan set kosong, jadi . Dan akhirnya kita membutuhkan seperangkat variabel untuk menunjukkan apakah setiap status NFA adalah status penerimaan NFA. Itu harus menjadi kasus bahwa pengkodean untuk setiap negara menerima DFA mengandung setidaknya satu negara menerima NFA dan bahwa pengkodean untuk setiap negara non-penerimaan DFA tidak mengandung negara menerima NFA jadi: untuk DFA menerima status dan untuk DFA yang tidak menerima .$x_0A + x_0B + \cdots + x_0D$$f_n$$x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$$i$$\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$$j$

Meminimalkan NFA adalah sulit, sangat sulit bahkan perkiraan itu sulit; lihat Meminimalkan NFA dan Ekspresi Reguler oleh Gramlich dan Schnitger (2005). Artikel ini tampaknya memiliki beberapa referensi yang berguna juga, misalnya Algoritma Pengurangan NFA oleh Sarana Ketidaksetaraan Reguler oleh Champarnaud dan Coulon (2002) yang berisi teknik minimalisasi.

Ada beberapa gagasan FSA kanonik yang belum tentu deterministik, karenanya dapat lebih kecil dari DFA minimal. Salah satu contoh adalah FSA "Residual", di mana seseorang dapat menghitung FSA residual kanonik secara langsung, lihat F. Denis, A. Lemay, dan A. Terlutte. "Residual finite state automata", Fundamenta Informaticae 51 (4): 339-368, 2002 . Ada beberapa alternatif.