✖

Überflüssige Zustände

Ein endlicher Automat kann Zustände haben, von denen aus man nie in einen Endzustand gelangen kann und die deshalb unnötig sind. Solche Zustände nennen wir überflüssige Zustände. Meist wollen wir sie entfernen, weil sie den ganzen Automaten nur unnötig komplizieren.

Beispiel überflüssiger Zustände

Wir betrachten diesen endlichen Automaten:

Wir sehen: Sobald wir in die Zustände q4 oder q5 gelangen, schaffen wir es nie wieder in einen der Endzustände q1 oder q2. Solche Zustände sind also überflüssig und wir können sie einfach entfernen. Dadurch erhalten wir einen neuen Automaten, der aber äquivalent wäre; er würde dieselbe Sprache akzeptieren. Nach dem Löschen der überflüssigen Zustände sähe der Automat so aus:

Er würde dabei dieselbe Sprache akzeptieren. Es gibt jedoch Situationen, in denen es sinnvoll ist, einige überflüssige Zustände zu behalten – zum Beispiel, wenn wir einen vollständigen Automaten konstruieren.

Definition eines überflüssigen Zustands

Gegeben sei ein endlicher Automat A = ⟨Q, Σ, δ, q0, F⟩. Wir sagen, dass ein Zustand q ∈ Q überflüssig ist, wenn es kein Wort w ∈ Σ∗ und keinen Zustand qf ∈ F gibt, sodass

⟨q,w⟩↦∗⟨qf,ε⟩.

So entfernt man überflüssige Zustände

Wir setzen voraus, dass die Eingabe ein Automat A = ⟨Q, Σ, δ, q0, F⟩ ist, der bereits keine unerreichbaren Zustände mehr hat. Wir suchen schrittweise die Zustände, die in Endzustände führen, dann die Zustände, die in Zustände führen, die in Endzustände führen, und so immer weiter. So erhalten wir die Menge aller Zustände, die nicht überflüssig sind. Am Anfang setzen wir S0 = F. Weitere Mengen Si für i ∈ ℕ konstruieren wir nach dieser Vorschrift:

Si={q∈Q|∃a∈Σ:δ(q,a)∈Si−1}∪Si−1

Die resultierende Menge aller Zustände, die nicht überflüssig sind, können wir so ausdrücken:

⋃i=1∞Si.

Und die Menge der überflüssigen Zustände als

Q∖⋃i=1∞Si.

Mit anderen Worten: Gilt Si = Si + 1, dann enthält die Menge Q ∖ Si die überflüssigen Zustände. Das Vorgehen veranschaulichen wir an diesem Automaten:

Zuerst setzen wir S0 = {q1, q2}. Dann bilden wir die Menge S1, indem wir zur Menge S0 alle Zustände hinzufügen, die in einen der Zustände der Menge S0 führen. Wir fügen also die Zustände q0 und q3 hinzu, weil von q0 ein Übergang nach q1 führt und von q3 ein Übergang nach q2. Wir erhalten S1 = {q0, q1, q2, q3}. Da S0 ≠ S1 gilt, machen wir weiter.

Wir bilden die Menge S2. Wir suchen also alle Zustände, von denen aus man nach S1 gelangen kann und die noch nicht in S1 liegen. Das ist nur der Zustand q6, von dem aus man in den Zustand q3 kommt. Wir erhalten S2 = {q0, q1, q2, q3, q6}. Da S1 ≠ S2 gilt, machen wir weiter.

Wir bilden die Menge S3. Gibt es einen neuen Zustand, von dem aus man in einen der Zustände in S2 gelangen kann? Nein: Von den Zuständen q4 und q5 kommt man in keinen der Zustände in S2, und die übrigen Zustände liegen schon in S2. Es gilt also S3 = {q0, q1, q2, q3, q6}. Da S2 = S3 gilt, endet der Algorithmus und die Menge S2 ist die Menge der Zustände, die nicht überflüssig sind. Die Menge {q4, q5} ist die Menge der Zustände, die überflüssig sind.

Formal konstruieren wir den neuen äquivalenten Automaten ohne überflüssige Zustände so: Wir haben den Automaten A = ⟨Q, Σ, δ, q0, F⟩ und konstruieren dazu den äquivalenten Automaten A′ = ⟨Q′, Σ, δ′, q0, F⟩ ohne überflüssige Zustände.

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), falls δ(q, a) ∈ Q′, sonst ist δ′(q, a) nicht definiert

Quellen

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