Diberikan dua string x dan y, saya ingin membangun DFA ukuran minimum yang menerima x dan menolak y. Salah satu cara untuk melakukan ini adalah pencarian brute force. Anda menghitung mulai DFA dengan yang terkecil. Anda mencoba setiap DFA sampai Anda menemukan satu yang menerima x dan menolak y.
Saya ingin tahu apakah ada cara lain yang diketahui untuk menemukan atau membangun DFA ukuran minimum yang menerima x dan menolak y. Dengan kata lain, dapatkah kita mengalahkan pencarian brute force?
Lebih detail:
(1) Saya benar-benar menginginkan sebuah algoritma untuk menemukan DFA ukuran minimum, bukan DFA ukuran minimum dekat.
(2) Saya tidak hanya ingin tahu seberapa besar atau kecil DFA minimumnya.
(3) Di sini, saya hanya fokus pada kasing seandainya Anda memiliki dua string x dan y.
Edit :
Informasi tambahan untuk pembaca yang tertarik:
Misalkan dan adalah string biner dengan panjang maksimal . Ini adalah hasil yang diketahui bahwa ada DFA yang menerima dan menolak dengan paling banyak menyatakan. Perhatikan bahwa ada sekitar DFA dengan alfabet biner dan paling banyak menyatakan. Oleh karena itu, pendekatan brute force tidak mengharuskan kita untuk menghitung lebih dari DFA. Oleh karena itu pendekatan brute force tidak bisa memakan waktu lebih dari waktu.y n x y √ n √ √ n √ n √
Slide yang saya temukan bermanfaat: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf
sumber
Jawaban:
Jika saya harus melakukan ini dalam praktek, saya akan menggunakan pemecah SAT.
Pertanyaan apakah ada DFA dengan menyatakan yang menerima x dan menolak y dapat dengan mudah dinyatakan sebagai instance SAT. Sebagai contoh, salah satu caranya adalah dengan memiliki 2 k 2 variabel boolean: z s , b , t benar jika DFA bertransisi dari state s ke state t pada bit input b . Kemudian tambahkan beberapa klausa untuk menegakkan bahwa ini adalah DFA, dan beberapa variabel dan klausa untuk menegakkan bahwa ia menerima x dan menolak y .k x y 2k2 zs,b,t s t b x y
Sekarang gunakan pencarian biner pada untuk menemukan k terkecil sehingga DFA semacam ini ada. Berdasarkan apa yang saya baca di makalah tentang masalah terkait, saya berharap ini mungkin cukup efektif dalam praktik.k k
Pengkodean lain dari SAT ini dimungkinkan. Sebagai contoh, kita dapat menggunakan pengkodean jejak:
Jika adalah panjang m , Anda bisa menambahkan m lg k variabel boolean: let s 0 , s 1 , ... , s m menjadi urutan negara dilalui pada input x , dan mewakili masing-masing s i menggunakan ⌈ lg k ⌉ variabel boolean.x m mlgk s0,s1,…,sm x si ⌈lgk⌉
Sekarang untuk setiap sehingga x i = x j , Anda memiliki batasan bahwa s i - 1 = s j - 1i,j xi=xj si−1=sj−1⟹si=sj
Semua persyaratan ini dapat dikodekan sebagai klausa SAT.
sumber