Konečné automaty
Úvod
Konečné automaty se dělí na determistické a nedetermistické. Deterministický konečný automat má pouze jeden počáteční stav a přechodová funkce jednoznačně určuje jeden následující stav. Zatímco nedeterministický konečný automat může mít více počátečních stavů a přechodová funkce udává celou množinu následujících stavů.
Slovo přijaté automatem je taková sekvence symbolů (ze vstupní abecedy), pro kterou automat skončí v koncovém stavu nebo v případě nedeterministického automatu v jednom z množiny následujících stavů.
Konečný automat je abstraktně definován množinou stavů, vstupní abecedou, přechodovou funkcí, počátečním stavem a koncovým stavem. V případě nedeterministického automatu množinou vstupních a množinou koncových stavů.
Definice konečného automatu
Formálně je konečný automat obecně definován jako uspořádaná pětice (Q, Σ, δ, q, F), kde:
- Q 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, popisující pravidla přechodů mezi stavy. Může mít buď podobu Q × Σ → Q (deterministický automat), nebo Q × {Σ ∪ ε} → P(Q) (nedeterministický automat).
- q je počáteční stav, q ∊ Q. (U nedeterministického automatu to může být i množina stavů.)
- F je množina finálních, akceptujících, stavů, F ⊆ Q.
Konkrétní příklad deterministického automatu:
Konečný automat A = ({q1, q2}, {a, b}, {δ(q1, a) = q2, δ(q1, b) = q1, δ(q2, a) = q1, δ(q2, a) = q2}, q1, q2).
Automat přijímá slova končící na lichý počet symbolů a.
Slova přijímaná tímto automatem A: {a, ba, aaa, aba, bba, aaba, abba, baaa, ...}
Slova nepřijatá tímto automatem A: {b, ab, aab, abb, baa, bab, aaaa, aaab, ...}
Protože je výše uvedený zápis již v tak jednoduchém případě velmi nepřehledný, používáme jiné způsoby popisu (reprezentace) konečných automatů.
Reprezentace konečného automatu tabulkou
První řádka tabulky označuje pro jednotlivé sloupce (mimo prvního) symboly vstupní abecedy Σ. V prvním sloupci tabulky jsou vyznačeny stávající stavy z abecedy Q. Ve zbývajících políčkách odečítáme, do jakého stavu automat přejde ze stávajícího stavu při daném symbolu na vstupu. U stávajících stavů jsou šipkami označeny počáteční a koncové stavy (v tomto případě jeden koncový stav). Šipka směrem ke stavu ukazuje, že v něm činnost automatu začíná a šipka od stavu, že je koncový, což znamená, že konečný automat danou posloupnost vstupních symbolů přijímá. Takový řetězec patří do jazyka přijímaného tímto automatem.
Reprezentace konečného automatu grafem
Uzly grafu reprezentují stavy konečného automatu, přechodovou funkci vyjadřují hrany označené symboly, koncový stav je vyjádřen zesílením uzlu a počáteční stav označen šipkou.
Reprezentace konečného automatu stavovým stromem
Kořen stromu je počáteční stav konečného automatu. Děti uzlu jsou stavy, na které se dostanu z nadřazeného uzlu. Koncové stavy jsou zvýrazněné podobně jako u grafu. Strom se dobře vytvoří z tabulky.
