Benutzer:A2r4e1/Baustelle-Minimalautomat

Quelle: |Deterministischer_endlicher_Automat#Minimierung

Minimierung

Zu jedem DEA existiert ein eindeutiger minimaler Automat, der die gleiche Sprache akzeptiert.

Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten $M$ akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:

$u\sim _{L(M)}v\Longleftrightarrow \forall w\in \Sigma ^{*}:uw\in L(M)\Leftrightarrow vw\in L(M)$

Sei $M=(Q,\Sigma ,\delta ,q_{0},F)$ ein deterministischer endlicher Automat. Dann ist $N=(Q',\Sigma ,\delta ',q'_{0},F')$ mit

• $Q'={\Big \{}[w]_{L(M)}\mid w\in \Sigma ^{*}{\Big \}}$
• $~q'_{0}=[\epsilon ]_{L(M)}$
• $~\delta '([u]_{L(M)},a)=[ua]_{L(M)}$
• $F'={\Big \{}[u]_{L(M)}\mid u\in L(M){\Big \}}$

der Äquivalenzklassenautomat zu $M$.

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen $F$ und $Q/F$. Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt bis sich keine Änderung mehr ergibt.