Simulace nedeterministického automatu

Pokud máme nedeterministický automat a chceme zjistit, zda přijímá dané slovo, můžeme automat převést na deterministický, můžeme 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. Zapamatujeme 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 ⟨{q₀}, 11001⟩. Začínáme ve stavu q₀ (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 q₀ je pouze jeden přechod pro symbol 1, takže se dostaneme do stavu q₁. Zapamatujeme si dvojici ⟨{q₁}, 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 q₀ a dále do stavu q₃. My se nyní vydáme do obou stavů zároveň. Zapamatujeme si tak dvojici ⟨{q₀, q₃}, 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 q₃, tak do stavu q₀. 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 q₀, tak na přechody z q₃. Ze stavu q₀ vedou přechody do stavů q₁ a q₂, ze stavu q₃ vede přechod zpět do q₁. Započítáme všechny tyto stavy, čímž získáme dvojici ⟨{q₁, q₂}, 01⟩:

Ještě jsme ale v tomto kroku neskončili. Vidíme, že ze stavu q₂ vede epsilon-přechod do stavu q₄. Víme, že po epsilon přechodu můžeme „jít kdykoliv“, aniž bychom četli další znak. Jinými slovy — aniž bychom přečetli další symbol ze vstupního slova, se můžeme ještě přesunout do stavu q₄. Přidáme tak stav q₄ mezi stavy, ve kterých se můžeme nacházet: ⟨{q₁, q₂, q₄}, 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ří stavů, ve kterých jsme. Z q₁ se nemůžeme přesunout nikam, protože chybí přechod pro 0. Výpočet v této větvi končí. Ze stavu q₄ se také nedostaneme nikam. Ze stavu q₂ se dostaneme zpátky do stavu q₂. Ale protože opět ze stavu q₂ vede epsilon-přechod do stavu q₄, můžeme se dostat i do stavu q₄. Z množiny stavů {q₁, q₂, q₄} se tak pro symbol 0 můžeme dostat do množiny stavů {q₂, q₄}, dostáváme dvojici ⟨{q₂, q₄}, 1⟩:

Nakonec máme na vstupu symbol 1. Ze stavu q₂ se nikam nedostaneme, výpočet v této větvi končí. Ze stavu q₄ se ale dostaneme do stavů q₃ a q₅. Dostáváme dvojici ⟨{q₃, q₅}, ε⟩:

Automat nyní přečetl celé slovo a „nachází se“ ve dvou stavech: q₃, q₅. 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 ⟨Q, Σ, δ, q₀, F⟩ 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{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Tuto funkci použijeme ve funkci, která bude simulovat činnost nedeterministického automatu. Vstupem je automat, vstupní slovo w = w₁w₂… w_n 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{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Pokud chceme ověřit, jestli automat přijímá slovo w, zavoláme funkci takto: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Zdroje

Kapitoly: Konečný automat, Totální automat, Nedeterministický konečný automat, Simulace NKA, Převod NKA na DKA

« Předchozí: Nedeterministický konečný automat

Další: Převod NKA na DKA »