Nedeterministický a deterministický konečný automat

Deterministický konečný automat (DKA, Deterministic finite automaton, DFA) je automat, který má konečné množství stavů a každý přechod je jednoznačný (neexistuje více možností přechodu z daného uzlu do jiných uzlů). Nedeterministický konečný automat (NKA, Non-deterministic finite automaton, NDFA) tuto podmínku nerespektuje, je zde tedy více možností, kam z daného uzlu při daném vstupu přejít. Nedeterministický automat je „inteligentní“ - půjde vždy takovým směrem, aby nakonec skončil v koncovém stavu (pokud mu to vstup umožňuje).

Z tohoto je zřejmé, že se daleko lépe vymýšlí nedeterministický automat, protože je jeho návrh daleko intuitivnější, ale na druhou stranu se výrayně hůře implementuje (vždy je zapotřebí jít všemi možnými směry, protože dopředu nevíme, který je správný, zároveň je pak tato implementace výpočetně náročnější).

Je ale dokázáno, že oba druhy automatů jsou stejně výpočetně silné a lze je mezi sebou převést.

Princip převodu

Samotný převod je stojí na myšlence, že pokud lze ze vstupního uzlu přejít jdo uzlu a do uzlu , tak vytvoříme nový uzel, říkejme mu . Tento uzel bude mít stejné vstupy a výstupy jako sjednocení uzlů a . Nyní tabulka převedeného automatu obsahuje dva uzly . Postup opakujeme pro uzel . Takto postupně projdeme všechny stavy nově vytvářenáho deterministického automatu.

Koncovými uzly převedeného deterministického automatu budou takové uzly, které jsou nadmnožinou koncových uzlů původního automatu (měl-li původně automat výstupní uzel , tak uzel , který vnikl jako sjednocení uzlu a uzlu , bude také výstupní).

Tento postup zároveň eliminuje všechny stavy, do kterých se deterministická verze automatu nemůže vůbec dostat. Zároveň ale mohou vzniknout uzly, které mají totožné vlastnosti (vstupní a výstupní uzly, konečnost, vlastnost být počátečním uzlem). Tyto uzly můžeme po doběhnutí algoritmu ztotožnit.

Příklad

Při konstrukci tabulky DKA z tabulky NKA postupujeme následovně.

1. Začínáme v počátečním uzlu S.
   
2. Z uzlu S můžeme při přechodu 0 do uzlů S a A, vytvořme tedy uzel [S, A], při přechodu 1 se vracíme do S.
3. Z uzlu [S, A] můžeme při přechodu 0 zpět do [S, A], protože tento přechod je v NDA definován u uzlu S a u uzlu A není definovám žádný přechod. Při přechodu 1 můžeme do uzlu S nebo B, což vyřešíme vytvořením uzlu [S, B].
   
4. Z uzlu [S, B] můžeme při 0 přejít do S a A (určuje uzel S) nebo C (určuje uzel B), vyřešíme vytvořením uzlu [S, A, C]. Při přechodu 1 přejdeme do S.
   
5. Z uzlu [S, A, C] můžeme přejít při 0 do [S, A], při 1 do [S, B].
6. Protože byl původně výstupním uzlem uzel C, tak je nyní výstupním uzlem uzel [S, A, C].

Převod nedeterministickáho automatu na deterministický