Lektion 1.2

Nichtdeterministische Automaten und die Potenzmengenkonstruktion

30 min Lesezeit

Einen DEA für „endet auf 0101" zu entwerfen war noch einfach. Schwieriger wird es bei Sprachen wie „der drittletzte Buchstabe ist eine 11". Du weißt beim Lesen nie, ob das gerade der drittletzte Buchstabe ist, und musst dir deshalb viele Möglichkeiten gleichzeitig merken. Der entsprechende DEA hat acht Zustände, obwohl die Sprache so einfach zu beschreiben ist.

Ein Gedankenexperiment hilft: Was, wenn der Automat an einer Stelle raten dürfte? Bei „der drittletzte Buchstabe ist 11" würde er bei jeder 11 einfach auf Verdacht annehmen, dass sie die drittletzte ist, und prüfen, ob danach genau noch zwei Zeichen folgen. Ein solcher Automat darf bei einem Zeichen mehrere Möglichkeiten haben. Das nennt man Nichtdeterminismus. Er macht Automaten oft viel kleiner und leichter zu entwerfen. Im Werkzeug Automaten-Simulator kannst du beides ausprobieren und siehst, wie sich mehrere aktive Zustände gleichzeitig verhalten.

Definition

Nichtdeterministischer endlicher Automat (NEA)

Ein NEA ist wie ein DEA ein Tupel (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F), nur dass die Übergangsfunktion jedem Paar aus Zustand und Zeichen eine Menge von Folgezuständen zuordnet, auch die leere Menge:

Es kann also pro Zeichen mehrere oder gar keine Übergänge geben. Der NEA akzeptiert ein Wort, wenn es mindestens einen Lauf gibt, der nach dem letzten Zeichen in einem Endzustand endet. Läufe, die in einer Sackgasse enden, sind ohne Bedeutung. Man kann sich vorstellen, dass der Automat sich bei jeder Wahl in mehrere Kopien aufspaltet, die alle parallel weiterlaufen.

δ:Q×Σ→P(Q)\delta: Q \times \Sigma \to \mathcal{P}(Q)
Beispiel

NEA für „endet auf 0101"

Der Automat hat drei Zustände. In q0q_0 bleibt er bei jedem Zeichen (00 und 11) und kann bei einer 00 zusätzlich nach q1q_1 raten, dass dies der Beginn des Suffixes 0101 ist. Von q1q_1 geht es bei einer 11 nach q2q_2, dem einzigen Endzustand. Sonst gibt es keine Übergänge.

δ(q0,0)={q0,q1},δ(q0,1)={q0},δ(q1,1)={q2},δ(q1,0)=δ(q2,⋅)=∅\delta(q_0, 0) = \{q_0, q_1\},\quad \delta(q_0, 1) = \{q_0\},\quad \delta(q_1, 1) = \{q_2\},\quad \delta(q_1, 0) = \delta(q_2, \cdot) = \emptyset

Das Wort 101101: Nach 11 ist die Menge der aktiven Zustände {q0}\{q_0\}. Nach 00 ist sie {q0,q1}\{q_0, q_1\}. Nach der letzten 11 führt q0q_0 nach q0q_0 und q1q_1 nach q2q_2, also {q0,q2}\{q_0, q_2\}. Da q2q_2 ein Endzustand ist, wird das Wort akzeptiert. Beim Wort 1010 endet die Menge in {q0,q1}\{q_0, q_1\} ohne Endzustand, es wird nicht akzeptiert.

Satz

Satz von Rabin und Scott

Zu jedem NEA gibt es einen DEA, der dieselbe Sprache erkennt. Nichtdeterminismus macht endliche Automaten also nicht mächtiger, nur möglicherweise kleiner: Der DEA kann bis zu 2n2^n Zustände haben, wenn der NEA nn Zustände hat.

L(NEA)=L(DEA),∣QDEA∣≤2∣QNEA∣L(\text{NEA}) = L(\text{DEA}), \qquad |Q_{\text{DEA}}| \le 2^{|Q_{\text{NEA}}|}
Beispiel

Potenzmengenkonstruktion für „endet auf 0101"

Wir starten bei {q0}\{q_0\} und berechnen nur die erreichbaren Mengen:

  • {q0}\{q_0\} mit 0→{q0,q1}0 \to \{q_0, q_1\} und mit 1→{q0}1 \to \{q_0\}
  • {q0,q1}\{q_0, q_1\} mit 0→{q0,q1}0 \to \{q_0, q_1\} (denn q1q_1 hat bei 00 keinen Nachfolger) und mit 1→{q0,q2}1 \to \{q_0, q_2\}
  • {q0,q2}\{q_0, q_2\} mit 0→{q0,q1}0 \to \{q_0, q_1\} und mit 1→{q0}1 \to \{q_0\}

Endzustand ist {q0,q2}\{q_0, q_2\}. Wir erhalten einen DEA mit drei Zuständen, der genau dem bekannten Automaten für „endet auf 0101" entspricht. Von den 23=82^3 = 8 möglichen Teilmengen waren nur 33 erreichbar. Das ist typisch, die theoretische Obergrenze wird selten erreicht.

Zusammenfassung

  • Ein NEA darf pro Zustand und Zeichen mehrere oder keine Folgezustände haben: δ:Q×Σ→P(Q)\delta: Q \times \Sigma \to \mathcal{P}(Q).

  • Er akzeptiert ein Wort, wenn mindestens ein Lauf in einem Endzustand endet.

  • Die Potenzmengenkonstruktion macht aus jedem NEA einen DEA mit denselben Wörtern, dessen Zustände Mengen von NEA-Zuständen sind.

  • Der DEA kann bis zu 2n2^n Zustände haben, meist sind deutlich weniger erreichbar.

  • NEAs sind nicht mächtiger als DEAs, aber oft viel kleiner und leichter zu entwerfen.

Übungen

Aufgabe 1Numerisch

Ein NEA hat 44 Zustände. Wie viele Zustände kann der DEA aus der Potenzmengenkonstruktion höchstens haben?

Aufgabe 2Multiple Choice

Der NEA für „endet auf 0101" liest das Wort 01010101. Welche Menge von Zuständen ist nach dem letzten Zeichen aktiv?

Aufgabe 3Numerisch

Der drittletzte Buchstabe eines Wortes über {0,1}\{0,1\} soll eine 11 sein. Wie viele Zustände hat der kleinste DEA für diese Sprache?

Aufgabe 4Freitext

Erkläre, warum Nichtdeterminismus bei endlichen Automaten die Menge der erkennbaren Sprachen nicht vergrößert.