Bagaimana cara membuktikan bahwa DFA dari NFA dapat memiliki jumlah negara eksponensial?

Semua automata terbatas non-deterministik dapat diubah menjadi automata terbatas deterministik yang setara. Namun, automata terbatas deterministik hanya memungkinkan satu panah per simbol yang menunjuk dari suatu negara. Oleh karena itu, negara-negara bagian tersebut harus menjadi anggota set kekuasaan negara-negara NFA. Ini tampaknya menunjukkan bahwa jumlah negara bagian DFA dapat diukur secara eksponensial dalam hal jumlah negara bagian NFA. Namun, saya bertanya-tanya bagaimana cara membuktikannya.

Satu operasi yang mengubah NFA menjadi NFA lain tetapi tidak melakukannya untuk DFA adalah pembalikan (arahkan semua panah ke arah sebaliknya, dan tukar negara awal dengan negara penerima). Bahasa yang dikenali oleh robot hasil transformasi adalah bahasa terbalik .$L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$

Jadi satu ide adalah mencari bahasa yang memiliki konstruksi asimetris. Ke depan, bahasa ini harus dikenali dengan memeriksa simbol pertama , hanya membutuhkan status . Untuk mundur, Anda harus menyimpan ingatan dari terakhirn + O ( 1 $n$$n + O(1)$ state, yang membutuhkan A n + O ( 1 ) menyatakan di mana A adalah ukuran alfabet.$n$$A^n + O(1)$$A$

Kami sedang mencari bahasa bentuk mana M n terdiri dari kata-kata dengan panjang n , S adalah himpunan bagian non-abjad dari alfabet, dan M ′ tidak memberikan batasan lebih lanjut. Kami mungkin juga memilih alfabet paling sederhana A = { a , b } (alfabet singleton tidak akan berhasil, Anda tidak mendapatkan NFA yang lebih kecil di sana) dan M ′ = A ∗ . S nontrivial S berarti S = { a } . Untuk$M_n S M'$$M_n$$n$$S$$M'$$\mathscr{A} = \{a,b\}$$M' = \mathscr{A}^*$$S$$S = \{a\}$ , kami mensyaratkan bahwa itu tidak berkorelasi dengan S (sehingga DFA untuk bahasa yang dibalik perlu menyimpan memori S ): ambil M n = A n .$M_n$$S$$S$$M_n = \mathscr{A}^n$

Jadi, biarkan . Ia dikenali oleh DFA sederhana dengan status n + 2 .$L_n = (a|b)^n a (a|b)^*$$n+2$

Membalikkannya menghasilkan NFA yang mengenali .$L_n^R = (a|b)^* a(a|b)^n$

The minimal DFA yang mengakui memiliki setidaknya 2 n + 1 negara. Hal ini karena semua kata-kata panjang 2 n + 1 harus mencapai negara yang berbeda di DFA. (Dengan kata lain, mereka termasuk kelas kesetaraan Myhill-Nerode yang berbeda .) Untuk membuktikan ini, ambil dua kata yang berbeda u , v ∈ A n + 1 dan biarkan k menjadi posisi di mana mereka berbeda ( u k ≠ v k ). Tanpa kehilangan umum, mari kita asumsikan u $L_n^R$$2^{n+1}$$2^{n+1}$$u,v \in \mathscr{A}^{n+1}$$k$$u_k \ne v_k$ dan v k = b . Maka u b k ∈ L R n dan v b k ∉ L R n ( b k adalah ekstensi yang membedakan u dan v ). Jika u dan v mengarah ke status yang sama dalam DFA yang mengenali L R n maka demikian juga u b k dan v b $u_k = a$$v_k = b$$u b^k \in L_n^R$$v b^k \notin L_n^R$$b^k$$u$$v$$u$$v$$L_n^R$$u b^k$$v b^k$, yang tidak mungkin karena yang satu mengarah ke negara penerima dan yang lainnya tidak.

Pengakuan: contoh ini dikutip di Wikipedia tanpa penjelasan. Artikel ini memberikan referensi ke artikel yang belum saya baca yang memberikan ikatan yang lebih ketat:
Leiss, Ernst (1981), "Representasi ringkas dari bahasa reguler oleh Boolean automata", Theoretical Computer Science 13 (3): 323–330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

Pertimbangkan rumpun bahasa berikut: $L_n = \{ x_1, x_2, \ldots, x_k \# x_{k+1}: \exists i \in \{1, \ldots, k\} \text{ with } x_i = x_{k+1} \}$

$L_n$$\{\#, 1,\ldots, n \}$

$O(n)$$L_n$$n$$i$$i$$3$

$L_n$$2^{O(n)}$$\{1,\ldots, n\}$

Saya cukup yakin buku Sipser memiliki contoh ini.

$n$$n$$2^n$

Contoh ini juga menunjukkan bahwa NFA mungkin menimbulkan ledakan eksponensial di bawah komplementasi. Memang, diketahui bahwa NFA (atau bahkan tata bahasa bebas konteks) untuk bahasa semua kata yang mengandung semua simbol alfabet harus memiliki jumlah negara yang eksponensial.