Základní pojmy
{{ term konecny-automat }} {{ term finite-automata-equal }}
Stav q ∈ Q je dosažitelný, pokud ∃w ∈ Σ*: (q0, w) ⊢*(q,ε). Jinak je stav nedosažitelný.
Začneme automat procházet od počátečního stavu (ten je vždy dosažitelný) a budeme sledovat, kam se z tohoto stavu lze dostat.
Stav q ∈ Q je užitečný, pokud ∃w ∈ Σ*: ∃p ∈ F:(q, w) ⊢*(p,ε). Jinak je stav zbytečný.
Algoritmus
Princip
Z automatu nejprve odstraníme všechny nedosažitelné a zbytečné stavy.
- Začneme tak tím, že vytvoříme dvě množiny stavů. Rozdělíme Q na podmnožinu nekoncových stavů Q1←Q\F a koncových stavů Q2←F.
- Doplníme přechodovou funkci s ohledem na nové pojmenování stavů.
- Zkontrolujeme, zdali všechny stavy v rámci jedné skupiny mají shodné přechody.
- Narazíme-li na stav, který se v rámci své skupiny svými přechody odlišuje, vytvoříme pro něj skupinu novou.
K zamyšlení
Jak velký může být výsledný DKA?