Algoritma apa yang ada untuk konstruksi DFA yang mengenali bahasa yang dijelaskan oleh regex yang diberikan?

Semua buku teks saya menggunakan algoritma yang sama untuk menghasilkan DFA diberi regex: Pertama, buat NFA yang mengenali bahasa regex, kemudian, dengan menggunakan konstruksi subset (alias "powerset"), ubah NFA menjadi DFA yang setara ( opsional meminimalkan DFA). Saya juga pernah mendengar seorang profesor menyinggung ada algoritma lain. Apakah ada yang mengetahui? Mungkin yang berjalan langsung dari regex ke DFA tanpa NFA perantara?

Ada berbagai algoritma untuk mengubah ekspresi reguler menjadi automata terbatas. Anda dapat langsung dari ekspresi reguler ke DFA tanpa membuat otomat lain terlebih dahulu dengan secara implisit melakukan konstruksi subset saat membuat automaton. Pilihan lain untuk secara langsung mendapatkan automata deterministik adalah dengan menggunakan metode derivatif.

Memeriksa apakah ekspresi reguler mewakili bahasa yang mengandung semua string adalah masalah lengkap PSPACE (lihat jawaban ini untuk referensi). Memeriksa apakah DFA menerima bahwa bahasa dapat dilakukan dalam waktu polinomial, jadi jika Anda langsung beralih dari ekspresi reguler ke DFA, akan ada ledakan di suatu tempat.

Pemahaman saya tentang literatur adalah bahwa kita dapat memilih terjemahan yang memungkinkan kita untuk melokalisasi ledakan. Artinya, ada berbagai cara untuk beralih dari ekspresi reguler ke otomat terbatas, dan metode yang linier, atau polinomial lebih disukai. Biasanya, biaya eksponensial didorong ke dalam penentuan automata.

Ada banyak pekerjaan mengidentifikasi sub-keluarga ekspresi reguler yang darinya kita dapat menghasilkan DFA secara efisien . Pekerjaan ini tergantung pada terjemahan yang Anda gunakan. Artinya, Anda memperbaiki pemetaan dari ekspresi reguler ke NFA dan mencoba untuk mengkarakterisasi ekspresi reguler yang memetakan ke DFA.

Konstruksi standar automata dari ekspresi reguler bukanlah konstruksi yang disukai dalam pekerjaan tersebut. Konstruksi pilihan menghasilkan automata yang sangat mirip dengan struktur ekspresi reguler. Konstruksi ini menggunakan gagasan turunan dari ekspresi reguler.

Turunan dari ekspresi reguler , JA Brzozowski. 1964.

$s$$r$$a$$r$$a$

Derivatif Parsial Ekspresi Reguler dan Konstruksi Finite Automata , V. Antimirov. 1995

Jika Anda menganggap keadaan otomat sebagai representasi dari semua string yang diterima dari keadaan itu, turunan (sebagian) memungkinkan Anda untuk memperlakukan ekspresi reguler sebagai keadaan . Berbeda dengan konstruksi buku teks standar yang secara intuitif memperlakukan ekspresi reguler sebagai automata, bukan negara.

Dari ekspresi reguler hingga automata deterministik , G. Berry dan R. Sethi, 1986.

Korespondensi antara ekspresi reguler dan keadaan otomaton dan determinisme dibahas secara eksplisit oleh Berry dan Sethi, yang menggabungkan gagasan turunan Brzozowski dengan gagasan untuk membedakan antara kemunculan simbol yang sama untuk memberikan terjemahan berbasis reguler dari sintaksis ekspresi reguler menjadi terbatas. automata.

Bahasa Reguler Satu-Tegas , A. Brüggemann-Klein dan Derick Wood, 1998.

Makalah ini dibangun di atas karya sebelumnya oleh Brüggemann-Klein dan mempelajari kasus-kasus di mana Anda dapat menggunakan turunan untuk menghasilkan DFA dalam waktu polinomial. Ada banyak pekerjaan setelah makalah ini. Itu signifikan dari perspektif teknologi web karena ekspresi reguler yang dapat dimanipulasi secara efisien (alias, sesuai dengan DFA) penting untuk memproses SGML dan XML.

Ada banyak pekerjaan yang mempelajari kasus khusus ekspresi reguler deterministik lainnya. Makalah yang sangat baru mempelajari ketika beberapa masalah ini dapat diselesaikan dalam waktu linier adalah dari 2012.

Ekspresi Reguler Deterministik dalam Waktu Linear , Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012