teoretický výpočetní model From Wikipedia, the free encyclopedia
Konečný automat (KA, též FSM z anglického finite state machine, či DFA z anglického deterministic finite automaton) je teoretický výpočetní model používaný v informatice pro studium formálních jazyků. Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu. Množina stavů je konečná (odtud název), konečný automat nemá žádnou další paměť, kromě informace o aktuálním stavu. Konečný automat je velice jednoduchý výpočetní model, dokáže rozpoznávat pouze regulární jazyky. Konečné automaty se používají při vyhodnocování regulárních výrazů, např. jako součást lexikálního analyzátoru v překladačích. V informatice se rozlišuje kromě základního deterministického či nedeterministického automatu také automat Mealyho a Mooreův.
Formálně je konečný automat definován jako uspořádaná pětice , kde:
Na počátku se automat nachází v definovaném počátečním stavu. Dále v každém kroku přečte jeden symbol ze vstupu a přejde do stavu, který je dán hodnotou, která v přechodové tabulce odpovídá aktuálnímu stavu a přečtenému symbolu. Poté pokračuje čtením dalšího symbolu ze vstupu, dalším přechodem podle přechodové tabulky atd.
Podle toho, zda automat skončí po přečtení vstupu ve stavu, který patří do množiny přijímajících stavů, platí, že automat buď daný vstup přijal, nebo nepřijal. Množina všech řetězců, které daný automat přijme, tvoří regulární jazyk.
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; musí platit, že ε ∉ Σ, protože by potom v definici - především 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í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žinou (ovšem tím vzroste počet stavů exponenciálně, na 2n). 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.
Jako příklad je možné ukázat následující deterministický konečný automat:
stav | 0 | 1 |
---|---|---|
S0 | S0 | S1 |
S1 | S2 | S0 |
S2 | S1 | S2 |
Pokud má daný automat zpracovat vstup 1011
, bude to probíhat takto: Na počátku je automat ve stavu S0. Na vstup přijde první symbol, jednička. Z tabulky vyplývá, že na příchod jedničky ve stavu S0 automat reaguje přechodem do stavu S1. Dále přichází nula, ze stavu S1 se příchodem nuly přechází do stavu S2. Poté přichází jednička, ze stavu S2 se příchodem jedničky přechází do stavu S2 (tzn. zůstává se ve stejném stavu). Nakonec přichází další jednička, takže automat opět zůstává ve stavu S2. Stav S2 nepatří do množiny A, tudíž tento automat vstup 1011
nepřijal, řetězec 1011
nepatří do jazyka přijímaného tímto automatem.
Pro úplnost: tento konečný automat přijímá regulární jazyk řetězců, které vyjadřují binární číslo dělitelné beze zbytku třemi. Číslo 10112 = 1110, číslo, které není dělitelné třemi (má zbytek 2, odpovídající výslednému stavu S2).
Místo relativně nepřehledného (zvláště pro větší automaty) popisu konečného automatu přímo tabulkou se obvykle používá grafické znázornění, na kterém kolečka znázorňují jednotlivé stavy a šipky (s přidruženým vstupním symbolem) mezi těmito kolečky popisují jednotlivé přechody. Příklad takového znázornění pro předchozí ukázkový automat je na obrázku:
Dvojité kolečko označuje přijímající stavy (v našem případě pouze jeden, S0), počáteční stav je označen šipkou směřující z volného prostoru k počátečnímu stavu (v našem případě je jím tedy S0), někdy s připsaným textem, např. START. (Tato notace není jediná, jindy se např. koncové stavy označují tlustším orámováním a dvojité kolečko označuje počáteční stav apod.)
Automat se zadává také pomocí regulárního výrazu, jejichž formalizmus má stejnou vyjadřovací sílu. Regulární výrazy (s rozšířeními) se používají v praxi pro zadávání automatů počítačům. (Častěji než tabulka nebo obrázek.)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.