Konwersja NKA na DKA

Pokazujemy, jak przekształcić automat niedeterministyczny w automat deterministyczny, udowadniając, że moc obliczeniowa automatów niedeterministycznych i deterministycznych jest równoważna.

Podstawowa idea

Rozważmy niedeterministyczny automat $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ bez przejść epsilon. Konstruujemy deterministyczny automat $\left<Q_D, \Sigma_D, \delta_D, p_0, F_D\right>$ taki, że

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

Definiujemy funkcję przejścia δ_D w następujący sposób:

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

Co to oznacza? Automat niedeterministyczny może znajdować się w wielu stanach jednocześnie, więc na przykład możemy dojść do sytuacji, w której nasz automat niedeterministyczny znajduje się w stanach {q₀, q₁}. Odczytując inny symbol, na przykład 1, możemy dojść do zbioru stanów {q₀, q₂, q₃}. W deterministycznej wersji tego samego automatu objawia się to poprzez utworzenie dwóch stanów, nazwanie ich {q₀, q₁} i {q₀, q₂, q₃} oraz wprowadzenie przejścia między nimi dla symbolu 1. Formalnie spowoduje to przejście z jednego stanu do drugiego, ale dzięki nazewnictwu będziemy wiedzieć, że w niedeterministycznym automacie bylibyśmy odpowiednio w dwóch lub trzech stanach.

Przykład

Rozważmy ten niedeterministyczny automat:

Aby skonstruować automat deterministyczny, musimy najpierw skonstruować nową funkcję przejścia. Aby to zrobić, potrzebujemy tabeli, w której zapiszemy wszystkie przejścia. Na początku tabela wygląda następująco:

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

W lewej kolumnie będziemy mieli wszystkie stany automatu deterministycznego na końcu algorytmu. Wypełniona tabela określi następnie funkcję przejścia. Teraz napiszemy w tabeli, do jakich stanów dojdziemy, jeśli jesteśmy w stanie {q₀}, a symbole wejściowe to 0 i 1.

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

Ze stanu q₀ przejście dla symbolu 0 prowadzi tylko do stanu q₁, natomiast dla symbolu 1 prowadzi do stanów q₁ i q₂. Teraz dodajemy do tabeli dwa nowe stany: {q₁} i {q₁, q₂}. Dlaczego? W momencie, gdy dodajemy do tabeli zestaw stanów, których nie mamy jeszcze w lewej kolumnie, dodajemy tam ten zestaw stanów.

$$ \begin{array}{c|c|c} \mbox{ Status }/\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 wypełniamy go ponownie. W przypadku stanu {q₁, q₂}, nie możemy zapomnieć o sprawdzeniu obu stanów, tj. gdzie otrzymujemy ze stanu q₁ z tym, gdzie otrzymujemy ze stanu q₂.

$$ \begin{array}{c|c|c} \mbox{ Status }/\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} $$

Mamy kilka nowych stanów do dodania do tabeli:

$$ \begin{array}{c|c|c} \mbox{ Status }/\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} $$

ponownie dodać przejścia:

$$ \begin{array}{c|c|c} \mbox{ Status }/\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ż tam są, więc dodamy tylko stan {q₀,q₁,q₂,q₃}.

$$ \begin{array}{c|c|c} \mbox{ Status }/\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 żadnego nowego stanu, więc tabela jest kompletna. Teraz wystarczy zbudować diagram. Stany automatu deterministycznego znajdują się w pierwszej kolumnie, a przejścia dla symboli 0 i 1 w pozostałych kolumnach. Każdy stan, który zawiera stan końcowy z oryginalnego automatu, będzie stanem końcowym w tym automacie. Oznacza to, że każdy stan zawierający q₃ będzie stanem końcowym. Automat będzie wyglądał następująco:

Możemy pokazać, że automat działa naprawdę dobrze. Jeśli spróbujemy zaakceptować słowo 11001. W automacie deterministycznym wybierzemy ścieżkę

$$ 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 zaakceptuje słowo, ponieważ ostatni stan {q₀, q₁, q₂, q₃} jest stanem końcowym. W niedeterministycznym automacie podczas symulacji dotarlibyśmy do tych samych stanów, tj. zaczęlibyśmy w stanie q₀ i dla symbolu 1 dotarlibyśmy do stanów {q₁, q₂}. Następny symbol 1 doprowadziłby nas do stanów {q₀,q₃} itd. dla kolejnych stanów. Ostatecznie znaleźlibyśmy się we wszystkich stanach {q₀, q₁, q₂, q₃} i automat zaakceptowałby słowo.

Źródła

• M. Sipser: Wprowadzenie do teorii obliczeń
• Aho, Sethi, Ullman: Kompilatory: zasady, techniki i narzędzia