PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Převod NKA na DKA

Zobrazit kapitoly článku
  1. Konečný automat
  2. Totální automat
  3. Nedeterministický konečný automat
  4. Simulace NKA
  5. 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 \subseteq 2^{Q_N}\)
  • \(\Sigma_D = \Sigma_N\)
  • p0 = {q0}
  • \(F_D = \left\{Q \in Q_D\,|\,Q \cap F_N \ne \emptyset\right\}\)

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 {q0, q1}. Přečtením dalšího symbolu, například 1, se můžeme dostat do množiny stavů {q0, q2, q3}. V deterministické verzi téhož automatu se to projeví tak, že vytvoříme dva stavy, pojmenujeme je {q0, q1} a {q0, q2, q3} 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 {q0} 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 q0 vede pro symbol 0 přechod jen do stavu q1, zatímco pro symbol 1 vede do stavů q1 a q2. Nyní přidáme do tabulky dva nové stavy: {q1} a {q1, q2}. 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 {q1, q2} nesmíme zapomenout zkontrolovat oba stavy, tj. kam se dostaneme ze stavu q1 sjednoceno s tím, kam se dostaneme ze stavu q2.

\[\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 {q0, q1, q3}, {q1} a {q1, q2} už tam máme, takže přidáme jen stav {q0, q1, q2, q3}.

\[\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í q3 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 {q0, q1, q2, q3} je koncový. V nedeterministickém automatu bychom se během simulace dostali do stejných stavů, tj. začali bychom ve stavu q0 a pro symbol 1 bychom se dostali do stavů {q1, q2}. Další symbol 1 by nás dostalů do stavů {q0, q3} atp. pro další stavy. Nakonec bychom se ocitli ve všech stavech {q0, q1, q2, q3} a automat by slovo přijal.

Zdroje #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace