Simulace nedeterministického automatu
Kapitoly: Konečný automat, Totální automat, Nedeterministický konečný automat, Simulace NKA, Převod NKA na DKA
Pokud máme nedeterministický automat a chceme zjistit, zda přijímá dané slovo, můžeme automat převést na deterministický, můžete to nějak vyzkoušet a nebo můžeme použít algoritmus, který bude simulovat činnost NKA.
Princip algoritmu
Princip si názorně ukážeme na vhodném příkladu. Mějme tento automat:
Jedná se o nedeterministický konečný automat, který přijímá nějaký jazyk. Vůbec nás teď nemusí zajímat jaký. Ukážeme si, jak může vypadat výpočet takového automatu pro vstupní slovo 11001. Úvaha bude taková, že zpracujeme symbol ze slova a podíváme se, kam všude můžeme díky vícenásobným přechodům pro stejný symbol jít. Zapamtujeme si všechny tyto stavy a v dalším kroku už budeme předpokládat, že jsme „ve všech těchto stavech současně“ a bude nás zajímat, kam se z těchto stavů můžeme dále dostat.
Budeme si tak pamatovat množinu stavů, ve kterých se můžeme nacházet a nepřečtenou část slova. Na začátku tak máme dvojici <{q0}, 11001>. Začínáme ve stavu q0 (počáteční stav) a na vstupu je slovo 11001. Automat vypadá takto, červeně a tučně je zvýrazněný stav, ve kterém jsme:
Prvním symbolem je 1, ze stavu q0 je pouze jeden přechod pro symbol 1, takže se dostaneme do stavu q1. Zapamatujeme si dvojici <{q1}, 1001>. Automat vypadá takto:
Pokračujeme dále. Nepřečtená část slova má tvar 1001, takže opět hledáme přechody pro 1. Ty už jsou dva — zpět do stavu q0 a dále do stavu q3. My se nyní vydáme do obou stavů zároveň. Zapamatujeme si tak dvojici <{q0, q3}, 001>.
Jakou to má logiku? My víme, že existuje cesta, jak se z počátečního stavu dostat pomocí slova 11 jak do stavu q3, tak to stavu q0. Zatím ještě nevíme, která větev se nám bude hodit, tak si zkrátka zapamatujeme obě. Pokračujeme dále. Máme na vstupu symbol 0. Nyní se musíme dívat jak na přechody z q0, tak na přechody z q3. Ze stavu q0 vede přechod do stavu q2, ze stavu q3 vede přechod zpět do q1. Započítáme oba stavy, čímž získáme dvojici <{q1, q2}, 01>:
Ještě jsme ale v tomto kroku neskončili. Vidíme, že ze stavu q2 vede epsilon-přechod do stavu q4. Víme, že po epsilon přechodu můžeme „jít kdykoliv“, bez toho, aniž bychom četli další znak. Jinými slovy — bez toho, aniž bychom přečetli další symbol ze vstupního slova se můžeme ještě přesunout do stavu q4. Přidáme tak stav q4 mezi stavy, ve kterých se můžeme nacházet: <{q1, q2, q4}, 01>. Automat bychom obarvili takto:
Dále je na vstupu 0. Podíváme se, kam se můžeme přesunout z těch třech stavů, ve kterých jsme. Z q1 se nemůžeme přesunout nikam, protože chybí přechod pro 0. Výpočet v této větvi končí. Ze stavu q4 se také nedostaneme nikam. Ze stavu q2 se dostaneme zpátky do stavu q2. Ale protože opět ze stavu q2 vede epsilon-přechod do stavu q4, můžeme se dostat i do stavu q4. Z množiny stavů {q1, q2, q4} se tak pro symbol 0 můžeme dostat do množiny stavů {q2, q4}, dostáváme dvojici <{q2, q4}, 1>:
Nakonec máme na vstupu symbol 1. Ze stavu q2 se nikam nedostaneme, výpočet v této větvi končí. Ze stavu q4 se ale dostaneme do stavů q3 a q5. Dostáváme dvojici $\left<\left\{q_3, q_5\right\}, \varepsilon\right>$:
Automat nyní přečetl celé slovo a „nachází“ ve dvou stavech: q3, q5. Protože alespoň jeden z nich je koncový stav, automat slovo 11001 přijímá.
Algoritmus
Jako první potřebujeme funkci, která bude brát jako parametr množinu stavů a spočítá, do kterých stavů se ještě můžeme dostat pomocí epsilon přechodů. Vstupem je tak automat $\left<Q, \Sigma, \delta, q_0, F\right>$ a množina stavů States a výstupem je nadmnožina těchto stavů, do kterých se lze dostat pomocí epsilon přechodů. Této operaci budeme říkat epsilon uzávěr množiny States.
$$\begin{align}\\ &\mathbf{Function} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, States\right)\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \left\{q\right\} \cup \delta(q, \varepsilon)\\ &\qquad \mathbf{EndFor}\\ &\qquad \\ &\qquad \mathbf{If} NextStates \setminus States = \emptyset \mathbf{Do}\\ &\qquad \qquad \mathbf{Return} States\\ &\qquad \mathbf{Else}\\ &\qquad \qquad \mathbf{Return} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{EndIf}\\ &\mathbf{EndFunction}\\ &\end{align}$$
Tuto funkci použijeme ve funkci, která bude simulovat činnost nedeterministického automatu. Vstupem je automat, vstupní slovo w = w1w2… wn a množina stavů, ve kterých se automat aktuálně nachází. Výstupem je buď odpověď Ano nebo Ne, podle toho, jestli automat přijímá nebo nepřijímá dané slovo.
$$\begin{align}\\ &\mathbf{Function} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, States\right)\\ &\qquad \mathbf{If} w = \epsilon \mathbf{Do}\\ &\qquad \qquad \mathbf{If} States \cap F \ne \emptyset \mathbf{Do}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{YES}\\ &\qquad \qquad \mathbf{Else}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{NO}\\ &\qquad \qquad \mathbf{EndIf}\\ &\qquad \mathbf{EndIf}\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \delta(q, w_1)\\ &\qquad \mathbf{EndFor}\\ &\qquad NextStates \leftarrow EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{Return} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w_2w_3\dots w_n, NextStates\right)\\ &\mathbf{EndFunction}\\ &\end{align}$$
Pokud chceme ověřit, jestli automat přijímá slovo w, zavoláme funkci takto: $ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, \left\{q_0\right\}\right)$.