Převod NKA na DKA

Ukážeme si, jak převést nedeterministický automat na determinitický automat, čímž dokážeme, že výpočetní síla nedeterministických automatů a deterministických je ekvivalentní.

Základní myšlenka

Mějme nedeterministický automat $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ bez epsilon přechodů. Sestavíme deterministický automat $\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 ≠ ∅}

Přechodovou funkci δ_D definujeme následovně:

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

Co to znamená? Nedeterministický automat může být zároveň ve více stavech, takže například se můžeme dostat do situace, kdy je náš nedeterministický automat ve stavech {q₀, q₁}. Přečtením dalšího symbolu, například 1, se můžeme dostat do množiny stavů {q₀, q₂, q₃}. V deterministické verzi téhož automatu se to projeví tak, že vytvoříme dva stavy, pojmenujeme je {q₀, q₁} a {q₀, q₂, q₃} a zavedeme mezi nimi přechod pro symbol 1. Formálně se tak dostaneme z jednoho stavu do druhého, ale díky pojmenování budeme vědět, že v nedeterministickém automatu bychom se ocitli ve dvou, respektive ve třech stavech.

Příklad

Mějme tento nedeterministický automat:

Abychom sestrojili deterministický automat, potřebujeme především sestrojit novou přechodovou funkci. K tomu nám pomůže tabulka, do které si zapíšeme všechny přechody. Na začátku vypadá tabulka takto:

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

V levém sloupečku budeme na konci algoritmu mít všechny stavy deterministického automatu. Vyplněná tabulka nám pak bude určovat přechodovu funkci. Nyní do tabulky zapíšeme, do jakých stavů se dostaneme, pokud jsme ve stavech {q₀} a na vstupu jsou symboly 0 a 1.

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

Ze stavu q₀ vede pro symbol 0 přechod jen do stavu q₁, zatímco pro symbol 1 vede do stavů q₁ a q₂. Nyní přidáme do tabulky dva nové stavy: {q₁} a {q₁, q₂}. Proč? Ve chvíli, kdy do tabulky doplníme nějakou množinu stavů, kterou ještě nemáme v levém sloupečku, tak tam tuto množinu stavů přidáme.

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

a opět vyplníme. U stavu {q₁, q₂} nesmíme zapomenout zkontrolovat oba stavy, tj. kam se dostaneme ze stavu q₁ sjednoceno s tím, kam se dostaneme ze stavu q₂.

$$ \begin{array}{c|c|c} \mbox{stav}/\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 jsme několik nových stavů, které musíme přidat do tabulky:

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

…a zase doplníme přechody:

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

Stavy {q₀, q₁, q₃}, {q₁} a {q₁,q₂} už tam máme, takže přidáme jen stav {q₀,q₁,q₂,q₃}.

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

Žádný nový stav už jsme nepřidali, takže tabulka je vyplněná. Nyní už jen sestavíme diagram. Stavy deterministického automatu jsou v prvním sloupci, přechody pro symboly 0 a 1 v dalších. Každý stav, který obsahuje nějaký koncový stav z původního automatu bude koncovým stavem i v tomto automatu. Tzn., že každý stav obsahující q₃ bude koncovým stavem. Automat bude vypadat takto:

Můžeme si ukázat, že automat funguje opravdu správně. Když zkusíme přijmout slovo 11001. V deterministickém automatu půjdeme cestou

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

a automat by slovo přijal, protože poslední stav {q₀, q₁, q₂, q₃} je koncový. V nedeterministickém automatu bychom se během simulace dostali do stejných stavů, tj. začali bychom ve stavu q₀ a pro symbol 1 bychom se dostali do stavů {q₁, q₂}. Další symbol 1 by nás dostalů do stavů {q₀,q₃} atp. pro další stavy. Nakonec bychom se ocitli ve všech stavech {q₀, q₁, q₂, q₃} a automat by slovo přijal.

Zdroje

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