Minimierung von Automaten

Unter der Minimierung eines Automaten verstehen wir das Finden eines äquivalenten Automaten, der die kleinstmögliche Anzahl von Zuständen enthält. Auch ein Automat, der keinen überflüssigen Zustand enthält, lässt sich noch weiter vereinfachen.

Beispiel

Nehmen wir diesen Automaten:

Der Automat akzeptiert nur die Wörter 01 und 11. Dabei ist offensichtlich, dass es einen einfacheren Automaten mit drei Zuständen gibt, der dieselbe Sprache akzeptiert. Die Zustände q₁ und q₂ lassen sich zu einem neuen Zustand {q₁, q₂} zusammenfassen. Die Übergänge, die in die Zustände q₁ oder q₂ führten, führen dann in den neuen Zustand, und dasselbe gilt für die Übergänge, die von q₁ und q₂ ausgehen. Wir erhalten diesen Automaten:

Dieser Automat akzeptiert offensichtlich dieselbe Sprache wie der vorherige und hat zugleich weniger Zustände.

Äquivalenz von Zuständen

Gegeben sei ein Automat A = ⟨Q, Σ, δ, q₀, F⟩. Wir definieren die Sprache eines Zustands q ∈ Q und bezeichnen sie mit L(q):

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Das heißt: Wir ändern den Startzustand des Automaten A von q₀ auf q und bestimmen die Sprache, die dieser Automat akzeptiert. Mit anderen Worten: Zur Sprache L(q) gehören alle Wörter w, für die man im Automaten A vom Zustand q aus mit dem Wort w in einen Endzustand des Automaten gelangt. Kehren wir zum vorherigen Automaten zurück, so gilt L(q₁) = {1}.

Wir sagen, dass zwei verschiedene Zustände q₁ und q₂ äquivalent sind, wenn gilt

$L (q_{1}) = L (q_{2})$

Was bedeutet das? Sind die Zustände q₁, q₂ äquivalent und machen wir sie zu Startzuständen des Automaten, dann erzeugen sie dieselbe Sprache. Mit anderen Worten: Gelangt der Automat in die Konfigurationen ⟨q₁, w⟩ und ⟨q₂, w⟩, dann muss er in beiden Fällen akzeptieren oder in beiden Fällen ablehnen.

Kehren wir zum vorherigen Automaten zurück: Die Zustände q₁ und q₂ sind äquivalent, denn wenn wir im Zustand q₁ sind, können wir das Eingabewort nur dann noch akzeptieren, wenn der ungelesene Teil des Wortes gleich 1 ist. Dasselbe gilt, wenn wir im Zustand q₂ sind.

Bei der Minimierung eines Automaten geht es also darum, äquivalente Zustände zu finden und diese Zustände zu entfernen, indem wir sie zu einem neuen Zustand zusammenfassen, genau wie im Beispiel oben.

So findet man äquivalente Zustände

Welche Zustände sind bestimmt nicht äquivalent? Nehmen wir einen Endzustand und einen Nicht-Endzustand, dann sind sie bestimmt nicht äquivalent, denn die Sprache des Endzustands unterscheidet sich von der Sprache des Nicht-Endzustands – ein Endzustand akzeptiert sicher das Wort ε, ein Nicht-Endzustand nicht. Das Vorgehen zeigen wir gleich an einem Beispiel. Gegeben sei dieser Automat:

Wir beginnen damit, dass wir zwei Zustandsmengen bilden

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Nun erstellen wir die Übergangstabelle und behalten die Information über die Gruppen S₁ und S₂ bei:

$\begin{array}{ccccc} Gruppe & Zustand & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ 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}$

Jetzt ändern wir die Tabelle so, dass wir nicht mehr direkt hinschreiben, in welche Zustände man für das jeweilige Symbol gelangt, sondern nur die Gruppe vermerken, in die wir übergehen. Zum Beispiel gelangen wir vom Zustand q₃ für 0 in den Zustand q₅, der in der Gruppe S₂ liegt. Statt q₅ schreiben wir also S₂ in die Tabelle:

$\begin{array}{ccccc} Gruppe & Zustand & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ 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}$

Nun teilen wir beide Gruppen weiter auf. In dieselbe Gruppe kommen jeweils Zustände, die für alle Symbole in dieselben Gruppen übergehen. Zum Beispiel liegen die Zustände q₃ und q₆ nicht in derselben Gruppe, denn weder für 0 noch für 1 gehen sie in dieselbe Gruppe. Dagegen liegen die Zustände q₁ und q₂ in derselben Gruppe, denn beide Zustände haben keinen Übergang für 0 und beide gehen für 1 in die Gruppe S₁. So bilden wir neue Gruppen:

$\begin{array}{ccccc} Gruppe & Zustand & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

In jeder Gruppe haben wir dieselben Übergänge. Die neu entstandenen Gruppen benennen wir und stellen wieder fest, in welche dieser neuen Gruppen die Zustände führen:

$\begin{array}{ccccc} Gruppe & Zustand & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Jetzt würden wir die Gruppen weiter aufteilen. Wir sehen aber, dass wir keine weitere Aufteilung mehr vornehmen können, wir würden dieselben Gruppen erhalten – denn die Zustände q₁ und q₂ haben zwar innerhalb der Gruppen dieselben Übergänge, liegen aber bereits in derselben Gruppe, und in der Gruppe S₄ gibt es keinen weiteren Zustand. Der Algorithmus zum Finden äquivalenter Zustände ist damit beendet. Aus jeder Gruppe genügt es, einen Zustand auszuwählen, die übrigen löschen wir, und alle Übergänge, die in gelöschte Zustände führten, führen dann in den einen Zustand, den wir ausgewählt haben.

Wir können uns also entscheiden, dass unser neuer Automat die Zustände q₃, q₆, q₀, q₁, q₄ hat und die Zustände q₂ und q₅ entfernt werden. Alle Übergänge, die nach q₂ führten, führen nun nach q₁, und alle Übergänge, die nach q₅ führten, führen nach q₄:

Vorgehen bei der Minimierung eines Automaten

Wir entfernen die unerreichbaren Zustände,
wir entfernen die überflüssigen Zustände,
wir entfernen die äquivalenten Zustände.

Quellen

Kapitel: Unerreichbare Zustände, Überflüssige Zustände, Minimierung von Automaten

« Zurück: Überflüssige Zustände

Weiter: Abgeschlossenheit regulärer Sprachen »