Minimierung des Automaten
Kapitoly: Unerreichbare Zustände, Redundante Zustände, Minimierung des Automaten
Mit der Minimierung eines Automaten ist gemeint, dass man einen äquivalenten Automaten findet, der die geringstmögliche Anzahl von Zuständen enthält. Auch ein Automat, der keine redundanten Zustände enthält, kann weiter vereinfacht werden.
Beispiel
Betrachten wir den folgenden Automaten:
Der Automat akzeptiert nur die Wörter 01 und 11. Es ist offensichtlich, dass es einen einfacheren Automaten mit drei Zuständen gibt, der dieselbe Sprache akzeptiert. Die Zustände q1 und q2 können zu einem neuen Zustand {q1, q2} zusammengefasst werden, und die Übergänge, die zu den Zuständen q1 oder q2 geführt haben, führen zu dem neuen Zustand, und dasselbe gilt für die Übergänge, die von q1 und q2 kommen. Wir erhalten diesen Automaten:
Dieser Automat akzeptiert offensichtlich die gleiche Sprache wie der vorherige, hat aber weniger Zustände.
Äquivalenz der Zustände
Betrachten wir den Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Wir definieren die Sprache des Zustands q∈ Q und bezeichnen L(q) als
$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$
Das heißt, wir ändern den Anfangszustand des Automaten A von q0 zu q und berechnen die von diesem Automaten akzeptierte Sprache. Mit anderen Worten: In der Sprache L(q) sind alle Wörter w so beschaffen, dass wir vom Zustand q für das Wort w zum Endzustand des Automaten A gelangen. Kehren wir zum vorherigen Automaten zurück, L(q1) = {1}.
Wir sagen, dass zwei verschiedene Zustände q1 und q2 äquivalent sind, wenn
$$ L(q_1) = L(q_2) $$
Was bedeutet das? Wenn die Zustände von q1, q2 äquivalent sind, dann erzeugen sie dieselbe Sprache, wenn wir sie zu den Anfangszuständen des Automaten machen. Mit anderen Worten: Wenn der Automat zu den Konfigurationen <q1, w> und <q2, w> gelangt, muss er in beiden Fällen entweder akzeptieren oder ablehnen.
Zurück zum vorherigen Automaten: Die Zustände q1 und q2 sind äquivalent, denn wenn wir uns im Zustand q1 befinden, können wir das Eingabewort nur akzeptieren, wenn der ungelesene Teil des Wortes gleich 1 ist. Das Gleiche gilt, wenn wir uns im Zustand q2 befinden.
Bei der Minimierung des Automaten geht es also darum, äquivalente Zustände zu finden und diese Zustände zu entfernen, indem man sie zu einem neuen Zustand zusammenfügt, so wie wir es im obigen Beispiel getan haben.
Wie man äquivalente Zustände findet
Welche Zustände werden sicherlich nicht äquivalent sein? Wenn wir einen Endzustand und einen Nicht-Endzustand nehmen, werden sie mit Sicherheit nicht äquivalent sein, weil die Sprache des Endzustands sich von der des Nicht-Endzustands unterscheidet - der Endzustand akzeptiert mit Sicherheit das Wort $\varepsilon$, der Nicht-Endzustand nicht. Wir werden das Verfahren gleich anhand eines Beispiels zeigen. Nehmen wir also diesen Automaten:
Wir beginnen damit, dass wir zwei Sätze von Zuständen erzeugen
\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}
Nun erstellen wir eine Übergangstabelle und halten die Informationen über die Gruppen S1 und S2 fest:
$$ \begin{array}{c|c|cc|c} \mbox{ Gruppe }&\mbox{ Status }&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} $$
Nun ändern wir die Tabelle so ab, dass wir nicht mehr direkt sagen, in welche Zustände ein bestimmtes Symbol übergeht, sondern nur noch die Gruppe angeben, in die wir übergehen. Zum Beispiel gehen wir vom Zustand q3 für 0 zum Zustand q5, der zur Gruppe S2 gehört. Statt q5 schreiben wir also S2 in die Tabelle:
$$ \begin{array}{c|c|cc|c} \mbox{ Gruppe }&\mbox{ Status }&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} $$
Nun teilen wir die beiden Gruppen weiter auf. Wir setzen die Zustände, die in dieselbe Gruppe gehören, immer für alle Symbole ein. Zum Beispiel werden die Zustände q3 und q6 nicht in der gleichen Gruppe sein, weil weder für 0 noch für 1 in die gleiche Gruppe gehen. Umgekehrt werden die Zustände q1 und q2 in der gleichen Gruppe sein, weil beide Zustände nicht für 0 übergehen und beide Zustände für 1 in die Gruppe S1 gehen:
$$ \begin{array}{c|c|cc|c} \mbox{ Gruppe }&\mbox{ Status }&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} $$
Wir haben in jeder Gruppe die gleichen Übergänge. Wir markieren die neu entstandenen Gruppen und finden wieder heraus, in welche dieser neuen Gruppen die Zustände gehen:
$$ \begin{array}{c|c|cc|c} \mbox{ Gruppe }&\mbox{ Status }&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} $$
An diesem Punkt nehmen wir eine weitere Aufteilung der Gruppen vor. Aber wir sehen, dass wir keine weitere Aufteilung mehr vornehmen können, wir würden die gleichen Gruppen erhalten - denn die Zustände q1 und q2 haben die gleichen Übergänge innerhalb der Gruppen, aber sie sind bereits in der gleichen Gruppe, und es gibt keinen weiteren Zustand in der Gruppe S4. Der Algorithmus zum Auffinden äquivalenter Zustände ist damit abgeschlossen. Wir müssen nur noch einen Zustand aus jeder Gruppe auswählen und die anderen löschen, und alle Zustände, die zu den gelöschten Zuständen geführt haben, führen zu dem einen Zustand, den wir ausgewählt haben.
Wir können also wählen, dass unser neuer Automat die Zustände q3, q6, q0, q1, q4 hat und die Zustände q2 und q5 löschen. Alle Übergänge, die zu q2 führten, führen nun zu q1 und alle Zustände, die zu q5 führten, führen zu q4:
Verfahren zur Minimierung von Automaten
- Entfernen Sie unerreichbare Zustände,
- Redundante Zustände entfernen,
- äquivalente Zustände entfernen.