Redundante Zustände
Kapitoly: Unerreichbare Zustände, Redundante Zustände, Minimierung des Automaten
Ein endlicher Automat kann Zustände haben, von denen es unmöglich ist, zu einem endlichen Zustand zu gelangen und die daher nutzlos sind. Wir nennen solche Zustände unerreichbare Zustände. In der Regel wollen wir diese Zustände entfernen, da sie den Automaten nur unnötig verkomplizieren.
Beispiel für überflüssige Zustände
Betrachten wir diesen endlichen Automaten:
Wir sehen, dass wir in dem Moment, in dem wir die Zustände q4 oder q5 erreichen, niemals einen der endlichen Zustände q1 oder q2 erreichen können. Diese Zustände sind so redundant, dass wir sie einfach entfernen können, wodurch wir einen neuen Automaten erhalten, der jedoch äquivalent ist; er würde die gleiche Sprache akzeptieren. Nach dem Löschen der redundanten Zustände würde der Automat wie folgt aussehen:
Er würde die gleiche Sprache akzeptieren. Es gibt jedoch Fälle, in denen es sinnvoll ist, einige redundante Zustände zu haben - zum Beispiel bei der Konstruktion eines Totalautomaten.
Definition eines redundanten Zustands
Betrachten wir einen endlichen Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Wir sagen, dass ein Zustand q ∈ Q redundant ist, wenn es kein Wort $w \in \Sigma^+$ und keinen Zustand qf ∈ F gibt, so dass
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
Wie man redundante Zustände entfernt
Nehmen wir an, wir haben einen Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$, der bereits frei von unerreichbaren Zuständen ist, als Eingabe. Wir werden nacheinander Zustände finden, die zu Endzuständen führen, und dann Zustände, die zu Zuständen führen, die zu Endzuständen führen, und so weiter und so fort. Auf diese Weise erhalten wir die Menge aller Zustände, die nicht redundant sind. Wir beginnen mit S0 = F. Wir werden weitere Mengen Si für i ∈ ℕ nach diesem Rezept konstruieren:
$$ S_i = \left\{q,|,\forall q \in Q, a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1} $$
Die resultierende Menge aller Zustände, die nicht redundant sind, kann wie folgt ausgedrückt werden:
$$ \bigcup_{i=1}^{\infty}S_i. $$
Und die Menge der redundanten Zustände als
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
Mit anderen Worten: Wenn Si = Si + 1 gilt, dann enthält die Menge Q∖ Si redundante Zustände. Wir werden das Verfahren mit dem folgenden Automaten veranschaulichen:
Zuerst setzen wir S0 = {q1, q2}. Als nächstes konstruieren wir die Menge S1, indem wir zur Menge S0 alle Zustände hinzufügen, die zu einem der Zustände in der Menge S0 führen. Wir fügen also die Zustände q0 und q3 hinzu, da q0 zu q1 und q3 zu q2 führt. Wir erhalten S1 = {q0, q1, q2, q3}. Da S0 ≠ S1 gilt, fahren wir fort.
Wir konstruieren die Menge S2. Wir suchen also nach allen Zuständen, von denen aus wir zu S1 gelangen können und die sich nicht in S1 befinden. Es gibt einen einzigen Zustand, q6, von dem aus wir zu q3 gelangen können. Wir erhalten S2 = {q0, q1, q2, q3, q6}. Da S1≠ S2, fahren wir fort.
Wir konstruieren die Menge S3. Gibt es einen neuen Zustand, von dem aus man zu einem der Zustände in S2 gelangen kann? Nein, von den Zuständen q4 und q5 kann man zu keinem der Zustände in S2 gelangen, und die anderen Zustände befinden sich bereits in S2. Es ist also wahr, dass S3 = {q0, q1, q2, q3, q6}. Seit S2 = S3 ist der Algorithmus beendet und die Menge S2 stellt die Menge der Zustände dar, die nicht redundant sind. Die Menge {q4, q5} ist die Menge der Zustände, die redundant sind.
Formal konstruieren wir einen neuen äquivalenten Automaten ohne redundante Symbole wie folgt. Wir haben einen Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$ und konstruieren dazu einen äquivalenten Automaten $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ ohne redundante Symbole.
- $Q^\prime = Q \setminus \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$