Saya tertarik pada algoritma yang efisien untuk persimpangan DFA untuk kasus khusus. Yaitu, ketika DFA untuk memotong mematuhi struktur tertentu dan / atau beroperasi pada alfabet terbatas. Apakah ada sumber di mana saya dapat menemukan algoritma kasus seperti itu?
Agar tidak membuat pertanyaan terlalu luas, struktur berikut ini sangat menarik: semua DFA untuk memotong beroperasi dalam alfabet biner (0 | 1), mereka juga dapat menggunakan simbol tidak peduli. Selain itu, semua negara hanya memiliki satu transisi kecuali untuk paling banyak negara khusus K, yang hanya memiliki dua transisi (dan transisi ini selalu 0 atau 1, tetapi tidak peduli). K adalah bilangan bulat, kurang dari 10 untuk tujuan praktis. Juga, mereka memiliki satu negara penerima. Selain itu, diketahui bahwa persimpangan SELALU DFA dalam bentuk "strip", yaitu, tidak ada cabang seperti pada gambar berikut:
EDIT: Mungkin deskripsi kendala pada input DFA tidak terlalu jelas. Saya akan mencoba memperbaikinya dalam paragraf ini. Anda memiliki sebagai input T DFA. Masing-masing DFA ini hanya beroperasi pada alfabet biner. Masing-masing dari mereka memiliki paling banyak N negara. Untuk setiap DFA, masing-masing negara bagian adalah salah satu dari yang berikut:
1) negara penerima (hanya satu dan tidak ada transisi dari itu ke negara lain)
2) negara dengan dua transisi (0 dan 1) ke negara target yang sama (mayoritas negara adalah jenis ini)
3) keadaan dengan dua transisi (0 dan 1) ke status target yang berbeda (paling banyak K dari jenis ini)
Dijamin bahwa hanya ada satu negara penerima dan bahwa ada paling banyak negara K tipe (3) di setiap input DFA. Hal ini juga dijamin bahwa persimpangan DFA dari semua DFAs masukan adalah "strip" (seperti dijelaskan di atas), ukuran kurang dari N .
EDIT2: Beberapa kendala tambahan, seperti yang diminta oleh DW dalam komentar:
- Input DFA adalah DAG.
- Input DFA "diratakan", mengikuti definisi DW dalam komentar. Yaitu, Anda dapat menetapkan bilangan bulat yang berbeda untuk setiap negara sedemikian rupa sehingga setiap transisi beralih dari bilangan bulat u ke bilangan bulat v , sehingga u + 1 = v .
- Jumlah menerima negara untuk setiap masukan DFA, tidak melebihi K .
Ada ide? Terima kasih.
sumber
a DFA in form of "strip", i.e., no branches
? Apakah Anda punya alasan khusus untuk percaya bahwa seseorang dapat melakukan lebih baik daripada algoritma standar dalam kasus Anda?Jawaban:
Karena itu, tidak , saya rasa tidak ada algoritma yang efisien untuk masalah Anda.
Perhatikan bahwa automata adalah pohon (dan karenanya DAG), diratakan, dan memiliki tiga status akhir. Sebenarnya, tiga kondisi terakhir tidak dapat digabung menjadi satu, jika ada yang puas dengan DAG. Selain itu, hanya dua negara bagian yang memiliki dua transisi keluar (berbeda).
sumber