Lucka Žoltá

Konečné automaty

Konečný automat (KA) tvoří množina stavů, vstupní abceda, přechodová funkce, počáteční a koncové stavy. Můžeme jej znázornit jako tabulku, graf či strom.

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 vrací jeden stav. Zatímco nedeterministický KA může mít více počátečních stavů a přechodová funkce vrací množinu stavů.

Slovo přijaté automatem je taková sekvence symbolů (ze vstupní abecedy), pro kterou automat skončí v koncovém stavu (příklad).

Regulární jazyk je takový jazyk (množina slov) který lze popsat konečným automatem.

Děfinice konečného automatu   : 

Konečný automat je uspořádaná pětice A (Q, Σ, δ, g₀, F), kde:

- Q je stavový prostor - konečná neprázdná množina stavů

- Σ je vstupní abeceda - konečná neprázdná množina vstupních symbolů

- δ je přechodová funkce - zobrazení δ: Q × Σ → Q, které na základě stavu a symbolu abecedy vrátí další stav

- g₀ je počáteční stav/y - g₀ ∈ Q

- F je množina koncových stavů - F ⊆ Q