2.2.2 Odstranění nedosažitelných a zbytečných stavů
Při optimalizaci konečného automatu rozlišujeme dva typy "nadbytečných" stavů.
Definice (Dosažitelný a nedosažitelný stav)
Dosažitelný a nedosažitelný stav
Dosažitelný stav je takový stav, pro který v automatu existuje posloupnost přechodů vedoucí z počátečního stavu právě do tohoto stavu.
Stav, který není dosažitelný, se nazývá nedosažitelný.
Důsledek
Nedosažitelné stavy lze z automatu odstranit, aniž by se změnil jazyk přijímaný daným automatem.
Definice (Užitečný a zbytečný stav)
Užitečný a zbytečný stav
Užitečný stav je takový stav, pro který v automatu existuje posloupnost přechodů vedoucí z tohoto stavu do některého z koncových stavů.
Stav, který není užitečný, se nazývá zbytečný.
Důsledek
Zbytečné stavy lze z automatu odstranit, aniž by se změnil jazyk přijímaný daným automatem. Jedinou výjimkou je případ, kdy je zbytečný počáteční stav automatu. Tím pádem jsou zbytečné či nedosažitelné i všechny zbylé stavy. V takovém případě ponecháme v automatu právě jeden stav (počáteční a nekoncový), jenž je z definice zbytečný. Jazyk přijímaný tímto automatem je prázdný.
Algoritmy pro odstranění stavů
Odstranění nedosažitelných stavů
Odstranění nedosažitelných stavů
Jak z konečného automatu odstraníme nedosažitelné stavy?
- Vytvoříme si prázdnou množinu, do které budeme postupně přidávat dosažitelné stavy.
- Nejprve přidáme počáteční stav, který je z definice vždy dosažitelný.
- Poté přidáme všechny stavy, jež jsou z tohoto stavu dosažitelné pomocí jednoho přechodu.
- Stejně pokračujeme pro všechny takto přidané stavy.
- Pokud už množinu dosažitelných stavů nelze rozšířit, algoritmus končí a stavy, jež nejsou v množině dosažitelných stavů, jsou nedosažitelné.
Odstranění zbytečných stavů
Jak z konečného automatu odstraníme zbytečné stavy?
- Vytvoříme si prázdnou množinu, do které budeme postupně přidávat užitečné stavy.
- Nejprve přidáme všechny koncové stavy, neboť ty jsou z definice vždy užitečné.
- Dále přidáme všechny stavy, ze kterých se lze za pomoci jednoho přechodu dostat do některého z užitečných stavů.
- Stejně pokračujeme pro všechny takto přidané stavy.
- Pokud už množinu užitečných stavů nelze rozšířit, algoritmus končí a stavy, které nejsou v množině užitečných stavů, jsou zbytečné.