Jak udowodnić, że DFA z NFA mogą mieć wykładniczą liczbę stanów?

Wszystkie niedeterministyczne skończone automaty można przekształcić w równoważne deterministyczne skończone automaty. Jednak deterministyczne automaty skończone zezwalają tylko na jedną strzałkę na symbol wskazującą na stan. Dlatego jego stany powinny należeć do zestawu sił stanów NFA. To wydaje się wskazywać, że liczba stanów DFA mogłaby się wykładniczo skalować pod względem liczby stanów NFA. Zastanawiałem się jednak, jak to udowodnić.

Jedną operacją, która przekształca NFA w inny NFA, ale nie robi tego w przypadku DFA, jest odwrócenie (skieruj wszystkie strzałki na odwrót i zamień stany początkowe na stany akceptujące). Językiem rozpoznawanym przez przekształcony automat jest język odwrócony .$L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$

Dlatego jednym z pomysłów jest poszukiwanie języka o asymetrycznej konstrukcji. Idąc dalej, język ten powinien zostać rozpoznany poprzez sprawdzenie pierwszych symboli, wymagających tylko stanów n + O ( 1 ) . Przechodząc do tyłu, należy zachować pamięć ostatnich n stanów, co wymaga stanów A n + O ( 1 ) , gdzie A jest rozmiarem alfabetu.$n$$n + O(1)$$n$$A^n + O(1)$$A$

Szukamy języka w postaci którym M n składa się ze słów o długości n , S jest nietrywialnym podzbiorem alfabetu, a M ′ nie zapewnia żadnych dalszych ograniczeń. Równie dobrze moglibyśmy wybrać najprostszy alfabet A = { a , b } (alfabet singleton nie da rady, nie ma tam mniejszych NFA) i M ′ = A ∗ . Nietuzinkowe S oznacza S = { a } . Jeśli chodzi o$M_n S M'$$M_n$$n$$S$$M'$$\mathscr{A} = \{a,b\}$$M' = \mathscr{A}^*$$S$$S = \{a\}$ , wymagamy, aby nie korelował on z S (aby DFA dla języka odwróconego musiał zachować pamięć S ): weź M n = A n .$M_n$$S$$S$$M_n = \mathscr{A}^n$

Zatem niech . Jest rozpoznawany przez prosty DFA ze stanami n + 2 .$L_n = (a|b)^n a (a|b)^*$$n+2$

Odwrócenie go daje NFA, który rozpoznaje .$L_n^R = (a|b)^* a(a|b)^n$

$L_n^R$$2^{n+1}$$2^{n+1}$$u,v \in \mathscr{A}^{n+1}$$k$$u_k \ne v_k$$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$, co jest niemożliwe, ponieważ jeden prowadzi do stanu akceptacji, a drugi nie.

Potwierdzenie: ten przykład był cytowany w Wikipedii bez wyjaśnień. Artykuł zawiera odniesienie do artykułu, którego nie przeczytałem, który ma ściślejszą
więź : Leiss, Ernst (1981), „Zwięzłe przedstawienie zwykłych języków przez automaty Boolean”, Theoretical Computer Science 13 (3): 323–330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

$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\}$

Jestem prawie pewien, że książka Sipsera ma ten przykład.

$n$$n$$2^n$

Ten przykład pokazuje również, że NFA mogą spowodować wykładniczy wybuch w wyniku komplementacji. Rzeczywiście wiadomo, że każdy NFA (lub nawet gramatyka bezkontekstowa) dla języka wszystkich słów zawierających wszystkie symbole alfabetu musi mieć wykładniczą liczbę stanów.