Pemisahan eksponensial antara NFA dan DFA di hadapan serikat pekerja

Baru-baru ini sebuah pertanyaan menarik diajukan dan kemudian dihapus.

Untuk bahasa biasa $L$, kompleksitas DFA -nya adalah ukuran DFA minimal yang menerimanya, dan kompleksitas NFA -nya adalah ukuran NFA minimal yang menerimanya. Sudah diketahui bahwa ada pemisahan eksponensial antara dua kompleksitas, setidaknya ketika ukuran alfabet tidak terikat. Memang, pertimbangkan bahasa $L_n$ atas alfabet $\{1,\ldots,n\}$ terdiri dari semua kata yang tidak mengandung semua simbol. Menggunakan teorema Myhill-Nerode mudah untuk menghitung kompleksitas DFA $2^n$ . Di sisi lain, kompleksitas NFA hanya $n$(jika beberapa negara awal diperbolehkan, jika tidak itu adalah ).$n+1$

Pertanyaannya dihapus menyangkut DFA meliputi kompleksitas dari bahasa, yang merupakan minimal sehingga L dapat ditulis sebagai (tidak harus saling lepas) serikat bahasa kompleksitas DFA paling C . DFA yang mencakup kompleksitas L n hanya 2 .$C$$L$$C$$L_n$$2$

Apakah ada pemisahan eksponensial antara kompleksitas NFA dan kompleksitas DFA?

Pertimbangkan bahasa , di mana # adalah simbol baru. Kompleksitas NFA dari M n adalah n . Kami akan menunjukkan bahwa kompleksitas penutupan DFA-nya adalah 2 n .$M_n = \epsilon +(L_n \#)^*L_n$$\#$$M_n$$n$$2^n$

Mari menjadi DFA menerima beberapa bahasa L ( A ) ⊆ M n , dengan fungsi transisi q A . Panggil negara yang layak jika ada beberapa kata w sehingga q A ( s , w ) adalah negara penerima. Untuk dua keadaan non-kegagalan s , t , misalkan A s , t = { w ∈ ( 1 + ⋯ + n ) ∗ : q $A$$L(A) \subseteq M_n$$q_A$$s$$w$$q_A(s,w)$$s,t$Tidak sulit untuk memeriksa bahwa setiap kata w ∈ L ( A ) dapat ditulis sebagai w = w 1 # ⋯ # w l di mana w i ∈ A s i , t i untuk beberapa s viable s i , t i .

$$A_{s,t} = \{ w \in (1+\cdots+n)^* : q_A(s,w) = t \}.$$ $w \in L(A)$$w = w_1\# \cdots \#w_l$$w_i \in A_{s_i,t_i}$$s_i,t_i$

Misalkan , di mana setiap A i adalah DFA. Biarkan P menjadi kisi yang dihasilkan oleh semua bahasa A i s , t . Kita dapat melihat L ( A i ) sebagai bahasa L P ( A i ) di atas P ∗ , ruang di antara dua simbol yang terkait dengan # . Di bawah sudut pandang ini, M $M_n = \bigcup_{i=1}^N L(A^i)$$A^i$$P$$A^i_{s,t}$$L(A^i)$$L_P(A^i)$$P^*$$\#$$M_n$sesuai dengan .$P^*$

Sebut universal jika untuk beberapa x ∈ P ∗ itu adalah kasus bahwa untuk semua y ∈ P ada z ∈ P ∗ sehingga x y z ∈ L P ( A i ) . Kami mengklaim bahwa beberapa L P ( A i ) adalah universal. Kalau tidak, setiap L P ( A i ) mengandung paling banyak ( |$L_P(A^i)$ $x \in P^*$$y \in P$$z \in P^*$$xyz \in L_P(A^i)$$L_P(A^i)$$L_P(A^i)$ kata panjang l . Secara total, L P ( A i ) harus mengandung semua | P | l kata-kata panjang l , maka | P | l ≤ N ( | P | - 1 ) l , yang dilanggar cukup besar l .$(|P|-1)^l$$l$$L_P(A^i)$$|P|^l$$l$$|P|^l \leq N (|P|-1)^l$$l$

$L_P(A^i)$$A = A^i$$x' \in P^*$$x \in M_n$$y \in L_n$$z_y \in M_n$$x\#y\#z_y \in L(A_i)$

$S \subseteq \{1,\ldots,n\}$$y_S$$S$$x\#y_S$$A$$S \neq T$$a \in S \setminus T$$x\#y_T y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \in L(A)$ while $x\#y_S y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \notin M_n$. Therefore $A$ must have a least $2^n$ states.