Konečný automat

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 vyčíslitelnosti a obecně 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í pro zpracování regulárních výrazů, např. jako součást lexikálního analyzátoru v překladačích. V informatice rozlišujeme automat Mealyho a Mooreův.

Formální definice[editovat | editovat zdroj]

Formálně je konečný automat definován jako uspořádaná pětice \left( S, \Sigma, \sigma, s, A \right), kde:

  • S je konečná neprázdná množina stavů.
  • Σ je konečná neprázdná množina vstupních symbolů, nazývaná abeceda.
  • σ je tzv. přechodová funkce (též přechodová tabulka), popisující pravidla přechodů mezi stavy. Může mít buď podobu S × Σ → S (deterministický automat), nebo S × {Σ ∪ ε} → P(S) (nedeterministický automat), viz níže.
  • s je počáteční stav, s ∈ S.
  • A je množina přijímajících stavů, A ⊆ S.

Popis činnosti automatu[editovat | editovat zdroj]

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.

Deterministické versus nedeterministické automaty[editovat | editovat zdroj]

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.

Ukázka činnosti[editovat | editovat zdroj]

Jako příklad je možné ukázat následující deterministický konečný automat:

S = (S0, S1, S2)
Σ = (0, 1)
σ viz tabulka:
stav 0 1
S0 S0 S1
S1 S2 S0
S2 S1 S2
s = S0
A = {S0}

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).

Znázornění konečného automatu[editovat | editovat zdroj]

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:

Ukázkové schéma automatu

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, 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.)

Odkazy[editovat | editovat zdroj]

Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Finite state machine ve Wikimedia Commons

Související články[editovat | editovat zdroj]