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

Odebráno 22 bajtů ,  před 12 lety
m
robot změnil: uk:Скінченний автомат; kosmetické úpravy
m ({{Formální jazyky a gramatiky}})
m (robot změnil: uk:Скінченний автомат; kosmetické úpravy)
'''Konečný automat''' ('''KA''', též '''FSM''' z anglického ''finite state machine'') je teoretický [[výpočetní model]] používaný v [[informatika|informatice]] pro studium [[vyčíslitelnost]]i a obecně [[formální jazyk|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í jazyk]]y. Konečné automaty se používají pro zpracování [[regulární výraz|regulárních výrazů]], např. jako součást [[Lexikální analýza|lexikálního analyzátoru]] v [[překladač]]ích. V informatice rozlišujeme automat [[Mealyho_automatMealyho automat| Mealyho]] a [[Mooreův stroj|Mooreův]].
 
== Formální definice ==
* ''S'' je konečná množina ''stavů''.
* ''Σ'' je konečná 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'' × {''Σ'' ∪ ε} → ''[[potenční množina|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 ==
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 ε ∉ ''Σ''). 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čí &bdquo;pouze&ldquo;„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.
 
== Ukázka činnosti ==
 
== Znázornění konečného automatu ==
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:
[[ImageSoubor:DFA example multiplies of 3.svg|500px|center|Ukázkové schéma automatu]]
 
Dvojité kolečko označuje přijímající stavy (v našem případě pouze jeden, S<sub>0</sub>), 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.)
[[th:เครื่องสถานะจำกัด]]
[[tr:Sonlu Durum Makinası]]
[[uk:Скінченний автомат]]
[[uk:Автомат скінченний]]
[[zh:有限状态自动机]]
172 107

editací