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

Přidáno 17 bajtů ,  před 11 měsíci
m
robot: přidáno {{Autoritní data}}; kosmetické úpravy
m (-Kategorie:Výpočetní modely, +Kategorie:Konečné automaty)
m (robot: přidáno {{Autoritní data}}; kosmetické úpravy)
 
'''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 [[informatika|informatice]] pro studium [[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í při vyhodnocová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 se rozlišuje kromě základního deterministického či nedeterministického automatu také automat [[Mealyho automat|Mealyho]] a [[Mooreův stroj|Mooreův]].
 
== Formální definice ==
== 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:
[[Soubor:DFA example multiplies of 3.svg|500px|centerstřed|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 směřující z volného prostoru k počátečnímu stavu (v našem případě je jím tedy S<sub>0</sub>), 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.)
 
== Související články ==
 
* [[Regulární výraz]]
* [[Regulární jazyk]]
 
== Externí odkazy ==
 
* {{commonscat}}
 
{{formální jazyky a gramatiky}}
{{Autoritní data}}
 
[[Kategorie:Konečné automaty]]
1 429 381

editací