Dua puluh tahun yang lalu, saya membangun paket ekspresi reguler yang mencakup konversi dari ekspresi reguler ke mesin keadaan terbatas (DFA) dan mendukung sejumlah operasi ekspresi reguler tertutup (bintang Kleene, penggabungan, pembalikan, set operasi, dll). Saya tidak yakin tentang kinerja terburuk dari paket saya.
DFA memiliki kekuatan ekspresif yang sama dengan NDFA, karena NDFA n-state dapat secara sepele dikonversi menjadi DFA yang memiliki 2 ^ n state. Namun, apakah ada jaminan batas atas yang lebih rendah untuk konversi yang tidak memerlukan ledakan eksponensial di negara bagian?
Saya tidak dapat menemukan contoh ekspresi reguler atau NDFA yang berperilaku buruk, tetapi saya tidak menghabiskan banyak waktu untuk memikirkannya. Saya menebak ekspresi reguler seperti ((((e | A | B | C) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) * yang mencampur banyak pergantian dan bintang-bintang Kleene akan memiliki NDFA yang berukuran linear tetapi DFA yang luas.
sumber
Jawaban:
Diketahui bahwa untuk setiap pasangan nomor naturals
n,a
sedemikian rupan <= a <= 2^n
, terdapat NDFA minimal dengann
status yang memiliki padanan minimal dfa minimum memilikia
status (lebih dari alfabet empat huruf).Lihat kertas di sini: Deterministik blow-up automata terbatas nondeterministic minimal atas alfabet tetap .
Abstrak makalah:
Jadi, saya kira jawaban untuk pertanyaan Anda adalah, tidak.
sumber
Contoh klasik untuk bahasa dengan pemisahan eksponensial antara ukuran DFA dan ukuran NFA adalah bahasa terbatas berikut: string biner dengan panjang tepat 2n di mana bagian pertama tidak sama dengan bagian kedua. NFA akan menebak indeks i di mana babak pertama dan kedua tidak setuju. Batas bawah untuk DFA mengikuti kompleksitas komunikasi, misalnya.
sumber
DFA minimum yang sesuai dengan NFA memiliki kondisi 2 ^ n terburuk, jadi Anda tidak dapat menjamin apa pun. Tanpa memiliki contoh konstruktif, alasannya adalah bahwa dalam NFA Anda dapat berada di setiap subset negara setelah membaca string input tertentu, dan setiap subset tersebut mungkin berperilaku berbeda ketika mengamati satu karakter. Misalkan bahasa dengan dua karakter dalam alfabet (a dan b), dan NFA N dengan n menyatakan yang dimulai dengan keadaan penerimaan di s_0. Sekarang menghitung semua himpunan bagian dari negara N, dan membangun tabel transisi sedemikian sehingga mengamati "a" dari subset S_i akan membawa Anda ke subset S_i + 1 dan mengamati b membawa Anda ke subset S_i-1 (ini bisa dilakukan untuk beberapa enumerasi, saya pikir ). Sekarang automata ini memiliki n menyatakan dan menerima urutan ma dan nb sedemikian sehingga mn = 0 mod 2 ^ | N |, dan tidak dapat diekspresikan dengan DFA yang memiliki kurang dari 2 ^ | N | menyatakan (karena mungkin perlu untuk menggilir semua himpunan bagian NFA N).
sumber