Konečný automat: Porovnání verzí

Přidáno 116 bajtů ,  před 11 lety
bez shrnutí editace
m (r2.6.4) (robot přidal: ko:유한 상태 기계)
Bez shrnutí editace
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řechodové funkce nebylo jasné, zda "ε" značí symbol z Σ, nebo prázdné slovo). Tyto tzv. ''epsilon-přechody'' automat provádí neustále, bez čtení symbolu ze vstupu. Je zřejmé, že teoreticky jich musí proběhnout nekonečné množství, ale prakticky to znamená, že automat přejde do takové množiny stavů, která odpovídá [[tranzitivní uzávěr|tranzitivnímu uzávěru]] přes tyto přechody.
 
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.
57

editací