Konečný automat (finite state machine) je model výpočtu, který se skládá z konečného množství stavů a přechodů mezi nimi. Automat přechází mezi stavy na základě symbolů čtených ze vstupu, případně při přechodu nějakým způsobem reaguje. Kromě údaje o aktuálním stavu neobsahuje automat žádnou další paměť.
Automat přechází mezi stavy na základě symbolů čtených ze vstupu. Rozlišují se dva základní typy konečných automatů: deterministický a nedeterministický.
Deterministický konečný automat (DKA)
Deterministický konečný automat je pětice ⟨Q, Σ, δ, q0, F⟩:
Q: konečná množina stavů
Σ: konečná vstupní abeceda
δ: Q x Σ → Q: přechodové funkce
q0 ∈ Q je počáteční stav
F ⊆ Q je množina koncových stavů
Nedeterministický konečný automat (NKA)
Nedeterministický konečný automat je pětice ⟨Q, Σ, δ, S, F⟩:
Q: konečná množina stavů
Σ: konečná vstupní abeceda
δ: Q x Σ → 2Q (do všech podmnožin Q): přechodové funkce
S ∈ Q je množina počátečních stavů
F ⊆ Q je množina koncových stavů
Srovnání DKA a NDA
Deterministický vyjadřuje, že v každém kroku výpočtu existuje nanejvíš jedna možnost kam se automat může posunout. Od nedeterministického se liší především definicí přechodové funkce a počátečním stavem. Užitečnou vlastností je, že nedeterministický konečný automat lze převést na deterministický - algoritmus.
Jak vypadá konečný automat
Konfigurace konečného automatu
Konfigurace automatu se skládá z aktuálního stavu automatu q a zbylé části vstupního řetězce w, kterou automat dosud nepřečetl.
Čtecí páskou rozumíme vstupní řetězec w. Automat má hlavu a ta čte symbol na pásce a pak se posune doprava.
DEFINICE:
Dvojice (q, w) ∈ Q x Σ* nazveme konfigurací konečného automatu M.
- (q0,w) nazveme počáteční konfigurací
- (q,ε), kde q ∈ F, nazveme koncovou konfigurací
Automat zpracuje vstup a řekne, že vstup w z toho jazyka je nebo není přijat. Jakmile dojede na konec vstupu, tak zkontroluje jestli jeho stav patří do množiny F, koncových stavů.
Tabulka
Možná víte, že relace můžeme pohodlně vyjádřit tabulkou.
Stavový diagram
Neformálně stavového diagramu
anglicky UML state machine
Jazyk přijimaný KA
Automat zpracuje vstup a řekne, že vstup z toho jazyka je nebo není přijat, podle toho, že jakmile dojede na konec vstupu, tak zkontroluje jestli jeho stav patří do množiny F, koncových stavů.
DEFINICE:
w ∈ Σ* je přijat konečným deterministickým automatem M, jestliže ∃(q0, w) |-* (q,ε) pro nějaké q ∈ F.
L(M) = {w: w ∈ Σ*, ∃q ∈ F: (q0, w) |-* (q,ε)} je jazyk přijimaný automatem M
(Kleeneova věta). Libovolný jazyk je regulární, právě když je přijímaný konečným automatem. Když není regulární jazyk, tak se pro něj nelze sestrojit konečný automat.
Úplně určený DKA
Automat se může dostat do stavu, odkud už nemá jak vygenerovat validní slovo (skončit), proto se tyhle přechody ani nepíšou. Můžeme, ale doplňit autoamt na úplně určený automat, kde se to bude otáčet, ale nesmí tento stav být koncovým stavem.
Deterministicky konečný automat, nazveme úplně určený, když zobrazení δ(q,a) je definováno pro všechny dvojice stavů q ∈ Q a vstupních symbolů a ∈ Σ
Motivace
Sekvenční obvody
Při konstrukci hardware se nejčastěji používají odvozené automaty typu Mealy a Moore.
Software
Syntaktická analýza
Softwarový návrh
Síťová komunikace
K zamyšlení
Jak velký může být výsledný DKA?
2n