2.2.6 Minimalizace deterministického konečného automatu
Cílem minimalizace je nalézt k danému DKA ekvivalentní automat s co nejmenším počtem stavů.
Ekvivalentní stavy
Ekvivalentní stavy jsou takové stavy konečného automatu, po jejichž sloučení se nezmění jazyk přijímaný daným konečným automatem. Dva stavy \(p, q\) jsou ekvivalentní (\(p \equiv q\)), pokud pro každé slovo \(w\) platí, že automat po přečtení \(w\) skončí v koncovém stavu, ať už vychází ze stavu \(p\) nebo \(q\) (nebo v obou případech skončí v nekoncovém).
Minimální DKA
Minimální deterministický konečný automat pro jazyk \(L\) je DKA s nejmenším možným počtem stavů přijímající jazyk \(L\).
Tento automat:
- nemá nedosažitelné stavy,
- nemá zbytečné stavy,
- nemá ekvivalentní stavy.
Jedinou výjimkou je automat přijímající prázdný jazyk. Minimální DKA přijímající prázdný jazyk má pouze jeden stav (počáteční a nekoncový), jenž je z definice zbytečný.
Unikátnost minimálního DKA
Minimální DKA lze sestrojit pro každý regulární jazyk, přičemž takový automat je pro každý regulární jazyk unikátní (až na případné pojmenování stavů).
Algoritmus minimalizace DKA
Jak převedeme deterministický konečný automat přijímající neprázdný jazyk na minimální?
- Z automatu odstraníme všechny nedosažitelné stavy.
- Z automatu odstraníme všechny zbytečné stavy.
- V automatu sloučíme všechny ekvivalentní stavy.
Postup hledání ekvivalentních stavů:
- Rozdělíme stavy do dvou skupin: koncové a nekoncové. (Počáteční stav nemá žádnou speciální skupinu, důležité je, zda je koncový či nikoliv).
- V každém kroku zkontrolujeme, zda všechny stavy v rámci jedné skupiny mají "shodné přechody" (tj. na stejný symbol přecházejí do stavů patřících do téže skupiny).
- Pokud narazíme na stav, který se v rámci své skupiny svými přechody odlišuje, vytvoříme pro něj (a další shodně se chovající stavy) novou skupinu.
- Algoritmus končí ve chvíli, kdy rozdělení stavů do skupin v daném kroku je stejné jako v kroku předchozím. Stavy, které zůstaly ve stejné skupině, jsou ekvivalentní a lze je sloučit.
Důležité: Nikdy se nemohou ve stejné skupině potkat koncové a nekoncové stavy.
Zjištění ekvivalence dvou automatů
Zjištění ekvivalence dvou automatů
Jak zjistíme, zda jsou dva konečné automaty ekvivalentní?
- Oba konečné automaty převedeme na deterministické a minimální.
- Mezi převedenými automaty se následně pokusíme najít izomorfismus.
- Jinými slovy, oba automaty musí mít stejný počet stavů (též stejný počet koncových stavů) a musí existovat takové mapování stavů, aby byla zachována i přechodová funkce.