Nedeterministický konečný automat
Kapitoly: Konečný automat, Totální automat, Nedeterministický konečný automat, Simulace NKA, Převod NKA na DKA
Konečný automat představený v minulých kapitolách (zkracujeme KA nebo DKA) byl vždy deterministický, což se projevovalo tím, že v každém okamžiku bylo jasné, co automat udělá. Nyní se podíváme na obecnější koncept nedeterministických konečných automatů (zkracujeme NKA), ve kterém mohou existovat přechody, které vychází ze stejného stavu a jsou pro stejný symbol.
Příklad
Podívejte se na následující diagram automatu:
Co je na něm zvláštní? Že z uzlu q0 vedou dvě hrany pro symbol 0. Pokud se tak pokusíme přijmout slovo 001, tak by se zdálo, že automat nebudete vědět, jestli má zůstat ve stavu q0 nebo jestli má následovat přechod do q1. Takový automat by byl nedeterministický.
Determinismus v tomto pojetí znamená, že v každé situaci je jasné, co automat udělá, není tam prostor pro nejednoznačnost. Deterministický automat má pro každý stav a každý symbol pouze jeden přechod. Nedeterminismus značí nejednoznačnost — z jednoho stavu mohou pro stejný symbol vést třeba tři přechody.
A jak se tedy automat rozhodne? Nedeterministický automat vždy zvolí (někdy taky říkáme „uhádne“) ten přechod, který povede k tomu, aby slovo přijal; pokud je to možné.
Pokud do automatu vložíme slovo 001, tak automat má tyto možnosti, jak se slovem naložit:
\begin{eqnarray} q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_0\\ q_0 \rightarrow q_0 \rightarrow q_1 \rightarrow q_2 \end{eqnarray}
plus možnosti, kdy nepřečte celé slovo. V první zůstával stále ve stavu q0, což určitě může, přechodová pravidla to dovolují. Ve druhé větvi se odvážil jít do dalších stavů a nakonec došel do stavu q2, který je koncový. V této větvi by automat slovo přijal. Nedeterministický automat vždy automaticky zvolí tu větev, ve které slovo přijme, pokud taková větev existuje.
Jak to udělá, že automaticky zvolí tu „příznivou“ větev? Můžeme si to představit tak, že nedeterministický automat projde všechny možné větve a pokud nalezne větev, ve které slovo přojímá, potom slovo přijme. Jak by mohl projít všechny větve? Zkrátka ve chvíli, kdy je ve stavu, ze kterého vede pro aktuální symbol n hran, tak automat n-krát nakopíruje sebe sama a každá kopie jde jinou cestou. Tím postupně projdeme všechny možnosti.
Stromová reprezentace výpočtu automatu
Mírně modifikujeme předchozí automat:
Nedeterminismus zůstává v prvním stavu. Předchozí automat přijímal všechna slova, která končí na 01. Tento modifikovaný automat přijímá všechna slova, která obsahují podslovo 01. Takže přijímá například slovo 101 nebo 0101. Všechny větve výpočtu si můžeme snadno vizualizovat pomocí stromu, např. pro slovo 01010 by strom mohl vypadat takto:
Na začátku jsme v počátečním stavu q0. Na vstupu máme slovo 01010, první nepřečtený znak je 0. Ze stavu q0 vedou dva přechody pro symbol 0, do stavů q0 a q1. Strom tak bude mít v tomto uzlu dva potomky: q0 a q1. Dále čteme symbol 1. Tam žádná nejednoznačnost není, přesuneme se do stavů q0 a q2. Dále čteme znak 0, v levé větvi opět nastává nejednoznačnost, rozdělíme výpočet do dvou další větví. V jedné opět zůstaneme v q0 a v další jdeme do q1. A tak dále.
Všimněte si, že celkem dvě větve končí ve stavu q2, v koncovém stavu. Existují dvě větve výpočtu, jak může automat přijmout dané slovo. Tento automat by tak slovo 01010 přijal. Můžeme zkusit vytvořit obdobný strom pro slovo 1000.
Výpočet buď zůstává ve stavu q0 nebo přejde do stavu q1, ale odtamtud už nemá kam dál jít, protože na vstupu už jsou samé nuly a stav q1 má přechod jen pro symbol 1. Žádná větev výpočtu nekončí v koncovém stavu, takže automat slovo 1000 nepřijímá.
Epsilon přechody
V nedeterministických automatech můžeme navíc ještě používat epsilon přechody. To jsou přechody, které můžeme provést, ať je na vstupu jakýkoliv symbol a to bez toho, aniž bychom nějaký symbol ze slova přečetli. Jak bychom mohli napsat nedeterministický automat, který by přijímal prázdné slovo, všechna slova skládající se jen z jedniček a slova tvaru 10n, tj. 10, 1010, …?
Rozdělili jsme automat na dva „podautomaty“. Horní se stará o to, aby poznal slova skládající se z 1, dolní se stará o slova tvaru 10n. Zkusíme přijmout slovo 111. Automat se na začátku nachází ve stavu q0 a na vstupu má slovo 111. Protože má k dispozici epsilon-přechody, může se rozhodnout přejít do stavu q1 nebo q2 podle toho, jak se mu to hodí. Vidíme, že se mu bude hodit přejít do stavu q1. Automat tam přejde. Přitom na vstupu má stále slovo 111! Až v tuto chvíli začne číst symboly ze slova a přecházet ze stavu q1 zase do q1, až přečte celé slovo a přijme ho.
Pokud bychom zkusili přijmout 1010, automat by na začátku přešel do stavu q2 a až odtud by začal zpracovávat symboly a opět by slovo přijal.
Pro slovo 1100 by mohl automat dělat cokoliv, takové slovo nemá jak přijmout.
Epsilon přechody a nedeterminismus nám v mnohém ulehčují práci, například důkaz toho, že sjednocení regulárních jazyků je zase regulární jazyk lze v epsilon přechody napsat mnohem jednošeji než v případě konečných automatů. V tomto důkazu jsme měli příklady těchto automatů
a
a dále jsme sestrojili konečný deterministický automat, který přijímal sjednocení obou jazyků. S epsilon přechody můžeme takový automat sestavit takto:
Zkrátka přidáme nový počáteční stav, z něj povedou dva epsilon přechody do původních počátečních stavů původních automatů a to je celé. Automat se nedeterministicky rozhodne, jestli zkusí slovo přijmout jedním nebo druhým „podautomatem“.
Definice nedeterministického automatu
Už jsme si ukázali, v čem se liší deterministický a nedeterministický konečný automat, zvýbá ho jen formalizovat. Deterministický konečný automat jsme definovali jako pětici $\left<Q, \Sigma, \delta, q_0, F\right>$, kde Q je množina stavů, $\Sigma$ je abeceda, δ je přechodová funkce, q0 je počáteční stav a F je množina koncových stavů. Jediné, co se změní v definici nedeterministických automatů je definice přechodové funkce.
V deterministické verzi mohla funkce pro volání δ(q, w) vrátit jen jeden stav, zatímco v nedeterministické verzi může vrátit více stavů — pokud je pro jeden symbol definováno více přechodů. Protože potřebujeme nadefinovat i epsilon-přechody, označíme si množinu $\Sigma\cup\left\{\varepsilon\right\}$ jako množinu $\Sigma_\varepsilon$, tj. $\Sigma_\varepsilon=\Sigma\cup\left\{\varepsilon\right\}$. Funkci δ tak definujeme jako
$$ \delta: Q \times \Sigma_\varepsilon\rightarrow 2^Q $$
To 2Q značí potenční množinu, množinu všech podmnožin množiny Q. Formalizace výpočtu je velmi podobná jako u konečných automatů. Konfigurace automatu je opět dvojice $\left<q, w\right> \in Q \times \Sigma^\ast$. Krok výpočtu $\mapsto$ je relace na množině konfigurací taková, že
$$ \left<q_i, w_0w_1\dots w_n\right> \mapsto \left<q_j, w_1\dots w_n\right>, $$
právě tehdy, pokud qj ∈ δ(qi, w0). V této větě byl největší rozdíl. V deterministických automatech jsme měli tuto podmínku zapsanou jako qj = δ(qi, w0), protože funkce δ vracela vždy jeden stav. Nedeterministická verze přechodové funkce vrací množinu stavů, proto je tam symbol ∈. Reflexivní a transitivní uzávěr relace budeme zase značit $\mapsto^\ast$. Řekneme, že automat přijímá slovo w právě tehdy, pokud existuje qf ∈ F takový, že
$$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>.$$