Minimalizace konečného automatu

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.

  1. 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.
  2. Doplníme přechodovou funkci s ohledem na nové pojmenování stavů.
  3. Zkontrolujeme, zdali všechny stavy v rámci jedné skupiny mají shodné přechody.
  4. 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?

Související