Przekształcenie NFA w DFA

Pokażemy, jak przekształcić automat niedeterministyczny (NFA) w automat deterministyczny (DFA) i w ten sposób udowodnimy, że moc obliczeniowa automatów niedeterministycznych i deterministycznych jest taka sama. Tę metodę nazywa się konstrukcją potęgową.

Główna idea

Weźmy automat niedeterministyczny $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ bez epsilon-przejść. Zbudujemy automat deterministyczny $\left<Q_D, \Sigma_D, \delta_D, p_0, F_D\right>$ tak, że

• Q_D ⊆ 2^Q_N
• $\Sigma_D = \Sigma_N$
• p₀ = {q₀}
• F_D = {Q ∈ Q_D,|,Q ∩ F_N ≠ ∅}

Funkcję przejścia δ_D definiujemy następująco:

$$ \forall Q \in Q_D, a\in\Sigma_D: \delta_D(Q, a) = \bigcup_{q\in Q} \delta_N(q, a) $$

Co to znaczy? Automat niedeterministyczny może być jednocześnie w kilku stanach, więc możemy na przykład trafić na sytuację, w której nasz automat niedeterministyczny jest w stanach {q₀, q₁}. Po przeczytaniu kolejnego symbolu, na przykład 1, możemy dostać się do zbioru stanów {q₀, q₂, q₃}. W deterministycznej wersji tego samego automatu objawi się to tak, że utworzymy dwa stany, nazwiemy je {q₀, q₁} i {q₀, q₂, q₃} i wprowadzimy między nimi przejście dla symbolu 1. Formalnie przechodzimy więc z jednego stanu do drugiego, ale dzięki nazwom będziemy wiedzieć, że w automacie niedeterministycznym znaleźlibyśmy się w dwóch, a potem w trzech stanach.

Przykład

Weźmy taki automat niedeterministyczny:

Żeby zbudować automat deterministyczny, musimy przede wszystkim zbudować nową funkcję przejścia. Pomoże nam w tym tabela, do której zapiszemy wszystkie przejścia. Na początku tabela wygląda tak:

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\} \end{array} $$

Na końcu algorytmu w lewej kolumnie będą wszystkie stany automatu deterministycznego. Wypełniona tabela będzie wtedy wyznaczać funkcję przejścia. Teraz wpiszemy do tabeli, do jakich stanów dostaniemy się, jeśli jesteśmy w stanach {q₀}, a na wejściu są symbole 0 i 1.

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \end{array} $$

Ze stanu q₀ dla symbolu 0 prowadzi przejście tylko do stanu q₁, natomiast dla symbolu 1 do stanów q₁ i q₂. Teraz dodamy do tabeli dwa nowe stany: {q₁} i {q₁, q₂}. Dlaczego? Kiedy tylko wpiszemy do tabeli jakiś zbiór stanów, którego nie mamy jeszcze w lewej kolumnie, dopisujemy ten zbiór stanów właśnie tam.

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}\\ \left\{q_1, q_2\right\} \end{array} $$

i znowu wypełniamy. Przy stanie {q₁, q₂} nie możemy zapomnieć sprawdzić obu stanów, czyli wziąć sumę zbioru stanów, do których dostaniemy się z q₁, i zbioru stanów, do których dostaniemy się z q₂.

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \end{array} $$

Dostaliśmy kilka nowych stanów, które musimy dodać do tabeli:

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}\\ \left\{q_0,q_3\right\}\\ \end{array} $$

…i znowu uzupełniamy przejścia:

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \end{array} $$

Stany {q₀, q₁, q₃}, {q₁} i {q₁,q₂} już mamy, więc dodamy tylko stan {q₀,q₁,q₂,q₃}.

$$ \begin{array}{c|c|c} \mbox{stan}/\mbox{symbol}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \left\{q_0,q_1,q_2,q_3\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \end{array} $$

Nie dodaliśmy już żadnego nowego stanu, więc tabela jest wypełniona. Teraz zostaje tylko narysować diagram. Stany automatu deterministycznego są w pierwszej kolumnie, przejścia dla symboli 0 i 1 w kolejnych. Każdy stan, który zawiera jakiś stan akceptujący pierwotnego automatu, będzie stanem akceptującym także w tym automacie. Czyli każdy stan zawierający q₃ będzie stanem akceptującym. Automat będzie wyglądał tak:

Możemy pokazać, że automat naprawdę działa poprawnie. Spróbujmy zaakceptować słowo 11001. W automacie deterministycznym pójdziemy drogą

$$ q_0 \rightarrow^1 q_1, q_2 \rightarrow^1 q_0, q_3 \rightarrow^0 q_1 \rightarrow^0 q_0, q_1, q_3 \rightarrow^1 q_0, q_1, q_2, q_3 $$

i automat zaakceptowałby słowo, bo ostatni stan {q₀, q₁, q₂, q₃} jest akceptujący. W automacie niedeterministycznym podczas symulacji dostalibyśmy się do tych samych stanów, czyli zaczęlibyśmy w stanie q₀ i dla symbolu 1 dostalibyśmy się do stanów {q₁, q₂}. Kolejny symbol 1 przeniósłby nas do stanów {q₀,q₃} i tak dalej dla kolejnych symboli. Na koniec znaleźlibyśmy się we wszystkich stanach {q₀, q₁, q₂, q₃} i automat zaakceptowałby słowo.

Źródła

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools