Minimalizace konečného deterministického automatu

• Konečné automaty nacházejí velmi široké uplatnění v technické praxi. Z hlediska efektivity a nákladnosti implementace je důležité, aby počet stavů byl pokud možno co nejmenší. Přirozeným problémem je proto konstrukce minimálního automatu, který rozpoznává daný regulární jazyk $L$.
• Minimální automat lze sestrojit poměrně jednoduchým způsobem - stačí mít k dispozici nějaký konečný automat, který rozpoznává $L$. Minimální automat pak obdržíme ztotožněním některých jeho stavů.

Nerozlišitelnost stavů

• Stavy $p,q\in Q$ v DFA A nazveme nerozlišitelné, právě když pro $\forall w\in {\Sigma }^{\ast }$ platí $\hat{\delta }(p,w)\in F\iff \hat{\delta }(q,w)\in F$

• Nerozlišitelnost stavů "$\equiv$" je binární relace na množině stavů $Q$, která je navíc ekvivalence

  • Pro každé $p,q,r\in Q$ platí
    • reflexivní: $p$ je nerozlišitelné s $p$
    • symetrická: když $p$ je nerozlišitelné s $q$, tak $q$ je nerozlišitelné s $p$
    • tranzitivní: když $p$ je nerozlišitelné s $q$ a $q$ je nerozlišitelné s $r$, pak $p$ je nerozlišitelné s $r$

• Pro stavy výsledného minimálního DFA $A_m$ platí, že jsou to třídy $\equiv$ a množina stavů $A_m$ tvoří rozklad $Q$ podle $\equiv$ (předpokládáme, že $A$ nemá nedosažitelné stavy)

Postup

• Minimální DFA $A_m$ lze vypočítat pomocí tabulky dvojic stavů, která zachycuje $\equiv$

1. Nejprve označíme všechny dvojice, které obsahují pouze jeden koncový stav
   • (Ty jsme schopni rozlišit hned na začátku)
2. Postupně označujeme dvojice $<p,q>$, pro které existuje $a\in \Sigma$ takové, že dvojice $<\delta (p,a),\delta (q,a)>$ už je označena
   • Tento krok opakujeme dokud ještě lze označit nějakou další dvojici
3. Neoznačené dvojice nejsme schopni rozlišit a pomocí tranzitivního uzávěru vypočítáme celou odpovídající třídu $\equiv$, kterou v $A_m$ sloučíme do jednoho stavu

Příklad

• minimalizujte DFA zadaný tabulkou

1. Označím dvojice $<p,q>$ takové, že $(p\in F\wedge q\notin F)\vee (p\notin F\wedge q\in F)$
2. Můj postup: Kouknu na volné místa (např. u dvojice $<1,6>$) a kouknu do tabulky, jaké dvojice by museli být označeny, abych mohl označit danou dvojici (tabulka říká buď $<2,6>$ nebo $<3,6>$. A zkontroluju jestli taková není už zaškrtlá (dvojici $<2,6>$ nemáme, ale dvojici $<3,6>$ máme zaškrtlou, takže můžu zašktnout i $<1,6>$). Když pro nějakou ještě nemám zašktnutou dvojici, tak počkám na konec, může se ještě objevit.)
3. 
4. 
5. 
6. Dvojice $<1,2>$ a $<3,4>$ jsou pro nás nerozlišitelné. Tedy výsledný automat je:

Navigace

Předchozí: Regulární výrazy, automaty s e-přechody Následující: Pumping lemma Celý okruh: 1. Teoretické základy informatiky