Proč máme dva druhy automatů? Lidem lépe navrhují nedeterministické automaty, protože jsou menší a jednodušší. Na druhou stranu se, ale často nedají implementovat. Existuje však způsob, jak využít obou vlasností. Můžeme nedeterministický automat jednoduše převést na deterministický.
Základní pojmy:
{{ term konecny-automat }}
{{ term finite-automata-equal }}
ε-přechod můžeme provést pro libovolný symbol na vstupu, přičemž při použití tohoto přechodu se ze vstupu žádný symbol nečte (čtecí hlava se neposouvá).
Ke každému nedeterministickému konečnému automatu M existuje ekvivalentní deterministický automat M'. NKA a DKA jsou výpočetně ekvivalentní.
Odstranění více počátečních stavů
NKA může mít z definice více počátečních stavů, DKA má jen jeden. Nový počáteční stav vytvoříme tak, že původní počáteční stavy považujeme za běžné a zavedeme si nový stav q0. Z nového počátečního stavu vedeme ε-přechody o všech původních počátečních stavů.
Algoritmus
- Prvním krokem determinizace je vytvoření nového startovacího symbolu q0, pokud má NKA jeden počáteční stav pak je tento stav novým startovacím stavem.
- Dále vyplníme množiny stavů pro každý terminál z každého stavu q' ∈ Q. Pokud některá tato množina obsahuje více než 1 prvek, pak z ní vytvoříme nový stav.
- Za koncové stavy označíme všechny ty, které obsahují koncový stav z původního NKA automatu.
Procedura Determinization
Vstup: NKA M = (Q, Σ, δ, S, F)
1. Q' ← {{q0}}
2. for ∀ q' ∈ Q do
3. δ'(q',a) ← ⋃p∈q′ δ(p,a), ∀a ∈ Σ
4. Q′←Q′∪ {δ′(q′, a): a ∈ Σ}
5. end for
6. q′0←{q0}
7. F′←{q′:q′∈Q′, q′∩F!=∅}
8. M′←(Q′,Σ, δ′, q′0, F′)
9. return M
K zamyšlení
Jak velký může být výsledný DKA?
Literatura: šestáková