Konečný automat: Porovnání verzí
Smazaný obsah Přidaný obsah
Řádek 17:
Přechodovou funkci lze definovat také tak, že v každém bodě tabulky není jeden cílový stav, ale celá množina stavů. Takový automat se nazývá ''nedeterministický konečný automat'' (oproti ''deterministickému konečnému automatu'', který v každém místě tabulky obsahuje právě jeden cílový stav). Takový hypotetický automat pak při přečtení jednoho symbolu ze vstupu přejde jakoby ''současně'' do všech stavů této množiny a ze všech těchto stavů pokračuje čtením dalšího vstupu. Vstup pak nedeterministický automat přijme tehdy, je-li alespoň jeden stav z těch, ve kterých automat nakonec zůstane, prvkem množiny přijímajících stavů.
V přechodové tabulce nedeterministického automatu je také navíc sloupeček pro ''prázdný vstup'', označovaný ε (ε obecně v celé teorii formálních jazyků označuje prázdné [[Slovo (formální jazyky)|slovo]]; musí platit, že ε ∉ ''Σ'', protože by potom v definici - především přechodové funkce - nebylo jasné, zda
Jakkoli se možnost současně provádět více větví výpočtu může zdát užitečná, ve skutečnosti je výpočetní model nedeterministického automatu úplně stejně mocný jako model deterministického automatu, také přijímá pouze regulární jazyk. Ve skutečnosti je relativně triviální převést libovolný nedeterministický automat na deterministický. K tomu stačí „pouze“ původní množinu stavů nahradit její [[potenční množina|potenční množinou]] (ovšem tím vzroste počet stavů [[exponenciála|exponenciálně]], na 2<sup>''n''</sup>). Každý stav takto vytvořeného automatu pak odpovídá nějaké množině stavů původního nedeterministického automatu a jsou mezi nimi jednoznačné přechody.
| |||