Äquivalenz von Zuständen

Definition

$A_q=(Q,\Sigma ,q,\delta ,F)$
Zwei Zustände $q,q^{\prime }\in Q$ heißen äquivalent ($q{\sim }_A{q}^{\prime }$) wenn
$L(A_q)=L(A_q^{\prime })$
$q{\sim }_A{q}^{\prime }\Rightarrow \forall a\in \Sigma :\delta (q,a){\sim }_A\delta (q^{\prime },a)$

siehe Äquivalenzrelation

Jede Äquivalenzklasse ist eine Menge von Objekten, die sich gleich verhalten.

Refinment Algorithmus

Beispiel

siehe Blatt blatt_06-0.pdf

Beweis