✖

Unerreichbare Zustände

Ein endlicher Automat kann Zustände haben, in die man nicht gelangen kann. Solche Zustände nennen wir unerreichbare Zustände. Diese Zustände wollen wir typischerweise entfernen, weil sie den ganzen Automaten nur unnötig verkomplizieren.

Beispiel unerreichbarer Zustände

Nehmen wir diesen Automaten:

Wir sehen, dass wir, egal was wir tun, nie in den Zustand q3 gelangen, weil kein Übergang zu ihm führt. Vom Zustand q3 sagen wir daher, dass er unerreichbar ist. Eine Frage – wäre der Zustand q3 erreichbar, wenn ein Übergang aus einem anderen Zustand zu ihm führen würde? Wenn wir eine Kante von einem der Zustände q0, q1, q2, q5 ziehen würden, wäre er erreichbar. Wenn wir einen weiteren Knoten hinzufügen und von ihm einen Übergang ziehen würden…

…dann wären natürlich beide Zustände q3 und q4 unerreichbar.

Definition eines unerreichbaren Zustands

Zuerst definieren wir den erreichbaren Zustand. Gegeben sei ein endlicher Automat A = ⟨Q, Σ, δ, q0, F⟩. Wir sagen, dass ein Zustand q ∈ Q erreichbar ist, wenn ein Wort w ∈ Σ∗ existiert, sodass

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

Ein Zustand q ∈ Q ist unerreichbar, wenn er nicht erreichbar ist.

Wie man unerreichbare Zustände entfernt

Wenn ein Automat bereits unerreichbare Zustände hat, ist es sinnvoll, sie zu entfernen. Wir konstruieren also einen äquivalenten Automaten A′ = ⟨Q′, Σ, δ′, q0, F′⟩, der keine unerreichbaren Zustände hat.

Wir bauen die Menge der erreichbaren Zustände iterativ auf. Wir beginnen mit der Menge S0 = {q0}, weil der Startzustand sicher erreichbar ist. Die nächste Menge bilden wir so:

Si={r∣δ(q,a)=r für ein q∈Si−1,a∈Σ}∪Si−1

In Worten: Die Menge S0 ist immer gegeben, die Menge S1 bilden wir so, dass wir alle Zustände aus der Menge S0 nehmen und herausfinden, wohin überall Übergänge für alle Symbole aus Σ führen. Diese Zustände vereinigen wir mit der ursprünglichen Zustandsmenge S0. Mit demselben Vorgehen bestimmen wir die Menge S2 und die weiteren. Offensichtlich gilt Si − 1 ⊆ Si.

Die Menge der erreichbaren Zustände erhalten wir dann so:

⋃i=1∞Si

Es mag seltsam aussehen, dass wir versuchen, unendlich viele Mengen Si zu vereinigen, aber der Automat enthält nur endlich viele Zustände. Das bedeutet, dass ab einem Zeitpunkt die Mengen Sj und Sj + 1 und alle weiteren gleich sind, sodass wir auch nach der Vereinigung unendlich vieler Mengen eine endliche Zustandsmenge erhalten können.

Kehren wir zum Automaten

zurück und versuchen, die Menge der erreichbaren Zustände zu finden. Wir beginnen mit dem Anfangswert

S0={q0}

Jetzt berechnen wir die Menge S1. Wir müssen alle Übergänge aus dem Zustand q0 finden und ihre Zielzustände zur Menge S0 hinzufügen. Weil q0 → a q1 und q0 → bq2 gilt, enthält die Menge S1 zusätzlich die Zustände q1 und q2:

S1={q0;q1;q2}

Als Nächstes konstruieren wir die Menge S2. Wir schauen, wohin wir überall aus den Zuständen q0, q1, q2 gelangen können. Der einzige neue Zustand ist q5, in den wir aus dem Zustand q1 gelangen können:

S2={q0;q1;q2;q5}

Als Nächstes bilden wir die Menge S3. Können wir aus den Zuständen q0, q1, q2, q5 in irgendeinen neuen Zustand gelangen? Nein, also enthält die Menge S3 dieselben Elemente wie S2:

S3={q0;q1;q2;q5}

Weil S2 = S3 ist, gilt auch S3 = S4 = S5 = … Wenn wir alle Si vereinigen, erhalten wir die Menge S2, weil in keiner weiteren Menge ein weiteres Element hinzukommt.

Die Menge der erreichbaren Zustände des Automaten ist also gleich {q0; q1; q2; q5}. Die unerreichbaren Zustände erhalten wir einfach als Differenzmenge:

Q∖⋃i=1∞Si

Die Menge der unerreichbaren Zustände unseres Automaten ist {q3; q4}. Wir entfernen aus dem Automaten A alle unerreichbaren Zustände und alle Übergänge, die irgendeinen unerreichbaren Zustand enthielten. Den äquivalenten Automaten ohne unerreichbare Zustände A′ = ⟨Q′, Σ, δ′, q0, F′⟩ zum Automaten A = ⟨Q, Σ, δ, q0, F⟩ definieren wir also so:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Quellen

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