Minimalizace automatu
Kapitoly: Nedosažitelné stavy, Nadbytečné stavy, Minimalizace automatu
Minimalizací automatu rozumíme nalezení ekvivalentního automatu, který obsahuje minimální možný počet stavů. I automat, který neobsahuje žádný nadbytečný stav, může být dále zjednodušen.
Příklad
Vezměme si tento automat:
automat přijímá jen slova 01 a 11. Přitom je evidentní, že existuje jednodušší automat se třemi stavy, který přijímá stejný jazyk. Stavy q1 a q2 lze spojit do jednoho nového stavu {q1, q2} a ty přechody, které vedly do stavů q1 nebo q2 povedou do nového stavu a totéž pro přechody vycházející z q1 a q2. Dostaneme tento automat:
Tento automat zjevně přijímá stejný jazyk jako předchozí a zároveň má méně stavů.
Ekvivalence stavů
Mějme automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Definujeme jazyk stavu q∈ Q, označíme L(q) jako
$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$
To jest změníme počáteční stav automatu A z q0 na q a spočítáme jazyk přijímaný tímto automatem. Jinými slovy v jazyku L(q) jsou všechna slova w taková, že se v automatu A dostaneme ze stavu q pro slovo w do koncového stavu automatu. Pokud se vrátíme k předchozímu automatu, tak L(q1) = {1}.
Řekneme, že dva různé stavy q1 a q2 jsou ekvivalentní, pokud platí
$$ L(q_1) = L(q_2) $$
Co to znamená? Pokud jsou stavy q1, q2 ekvivalentní, tak pokud z nich učiníme počáteční stavy automatu, tak budou generovat stejný jazyk. Jinými slovy: pokud se automat dostane do konfigurace <q1, w> a <q2, w>, tak musí v obou případech buď přijmout nebo v obou případech zamítnout.
Pokud se vrátíme k předchozímu automatu: stavy q1 a q2 jsou ekvivalentní, protože pokud jsme ve stavu q1, tak už můžeme přijmout vstupní slovo jen tehdy, pokud je nepřečtená část slova rovna 1. Totéž, pokud jsme ve stavu q2.
Při minimalizaci automatu tak jde o to nalézt ekvivalentní stavy a tyto stavy odstranit tak, že je sjednotíme do jednoho nového stavu stejně, jako jsme to udělali v příkladu výše.
Jak nalézt ekvivalentní stavy
Jaké stavy jistě nebudou ekvivalentní? Pokud vezmeme koncový a nekoncový stav, tak jistě nebudou ekvivalentní, protože jazyk koncového stavu je různý od jazyku nekoncového stavu — koncový stav určitě přijímá slovo $\varepsilon$, nekoncový nikoli. Postup si rovnou ukážeme na příkladu. Mějme tak tento automat:
Začneme tak tím, že vytvoříme dvě množiny stavů
\begin{eqnarray} S_1&=&F=\left\{q_3, q_6\right\},\\ S_2&=&Q\setminus F=\left\{q_0, q_1, q_2, q_4, q_5\right\}. \end{eqnarray}
Nyní vytvoříme tabulku přechodů a zachováme informaci o skupinách S1 a S2:
$$ \begin{array}{c|c|cc|c} \mbox{skupina}&\mbox{stav}&0&1\\\hline S_1&q_3&q_5&q_4\\ &q_6&—&—\\\hline S_2&q_0&q_1&q_2\\ &q_1&—&q_3\\ &q_2&—&q_3\\ &q_4&q_6&—\\ &q_5&q_6&—\\ \end{array} $$
Teď tabulku upravíme tak, že místo toho, abychom měli v tabulce přímo napsáno, do jakých stavů se pro daný symbol jde, tak si tam poznamenáme pouze skupinu, do které přecházíme. Například ze stavu q3 se pro 0 dostaneme do stavu q5, který je ve skupině S2. Místo q5 tak napíšeme do tabulky S2:
$$ \begin{array}{c|c|cc|c} \mbox{skupina}&\mbox{stav}&0&1\\\hline S_1&q_3&S_2&S_2\\ &q_6&—&—\\\hline S_2&q_0&S_2&S_2\\ &q_1&—&S_1\\ &q_2&—&S_1\\ &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$
Nyní dále rozdělíme obě skupiny. Do stejných skupin dáme vždy stavy, které přecházejí do stejných skupin pro všechny symboly. Například stavy q3 a q6 nebudou ve stejné skupině, protože ani pro 0 anmi pro 1 nejdou do stejné skupiny. Naopak stavy q1 a q2 budou ve stejné skupině, protože oba stavy nemají přechod pro 0 a oba stavy jdou pro 1 do skupiny S1. Vytvoříme tak nové skupiny:
$$ \begin{array}{c|c|cc|c} \mbox{skupina}&\mbox{stav}&0&1\\\hline &q_3&S_2&S_2\\\hline &q_6&—&—\\\hline &q_0&S_2&S_2\\\hline &q_1&—&S_1\\ &q_2&—&S_1\\\hline &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$
V každé skupině máme stejné přechody. Nově vzniklé skupiny označíme a opět zjistíme, do které z těchto nových skupin stavy směřují:
$$ \begin{array}{c|c|cc|c} \mbox{skupina}&\mbox{stav}&0&1\\\hline S_1&q_3&S_5&S_5\\\hline S_2&q_6&—&—\\\hline S_3&q_0&S_4&S_4\\\hline S_4&q_1&—&S_1\\ &q_2&—&S_1\\\hline S_5&q_4&S_2&—\\ &q_5&S_2&—\\ \end{array} $$
V tuto chvíli provedeme další dělení skupin. Vidíme ale, že už žádné další dělení provést nemůžeme, získali bychom stejné skupiny — protože stavy q1 a q2 mají sice stejné přechody v rámci skupin, ale už jsou ve stejné skupině a žádný další stav ve skupině S4 není. Algoritmus hledání ekvivalentních stavů je u konce. Z každé skupiny nám stačí vybrat jeden stav, ostatní smažeme a všechny stavy, které vedly do smazaných stavů, povedou do toho jednoho stavu, který jsme vybrali.
Můžeme si tak vybrat, že náš nový automat bude mít stavy q3, q6, q0, q1, q4 a stavy q2 a q5 odstraníme. Všechny přechody, které vedly do q2 nyní povedou do q1 a všechny stavy, které vedly do q5 povedou do q4:
Postup minimalizace automatu
- Odstraníme nedosažitelné stavy,
- odstraníme nadbytečné stavy,
- odstraníme ekvivalentní stavy.