NEA / NFA — Nichtdeterministische endliche Automaten

Endliche Automaten mit mehreren erlaubten Nachfolgezuständen pro Eingabesymbol; akzeptieren ein Wort, sobald mindestens ein Berechnungspfad in einen Endzustand führt. Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben.

1. Definitionen und Formalismen

2. Kernkonzepte und Vorgehen

Ein Wort schrittweise durchführen

1. Starte mit der Menge $Q_0 = S$ (bei $\varepsilon$-NEA: $\varepsilon\text{-cl}(S)$). Notiere sie als Wurzel des Baumes.
2. Für jedes Symbol $a$ des Wortes: bilde die Vereinigung aller $\delta(q, a)$ über $q \in Q_i$. Das ist die neue aktive Menge $Q_{i+1}$.
3. Bei $\varepsilon$-NEAs schließe nach jedem Schritt den $\varepsilon$-Abschluss an: $Q_{i+1} := \varepsilon\text{-cl}(Q_{i+1})$.
4. Nach Verarbeitung des kompletten Wortes: prüfe, ob $Q_n \cap E \neq \emptyset$. Falls ja, akzeptiert; falls nein, verwerfen.
5. Alternativ: zeichne einen Baum, in dem jeder Knoten einen aktuellen Zustand und jede Kante einen möglichen Übergang darstellt. Ein akzeptierender Pfad genügt.

Potenzmengenkonstruktion (NEA $\to$ DEA)

1. Zustände des DEAs sind Teilmengen von $Z$, also Elemente von $\mathcal{P}(Z)$. Im Worst Case gibt es $2^{|Z|}$ davon.
2. Startzustand ist $S$ (bzw. $\varepsilon\text{-cl}(S)$).
3. Übergangsfunktion des DEAs: $\delta'(Q, a) = \bigcup_{q \in Q} \delta(q, a)$. Bei $\varepsilon$-NEAs zusätzlich $\varepsilon$-Abschluss anschließen.
4. Endzustände sind alle Teilmengen $Q \subseteq Z$ mit $Q \cap E \neq \emptyset$.
5. In der Praxis konstruiert man nur die vom Startzustand erreichbaren Teilmengen — meist sehr viel weniger als $2^{|Z|}$.

3. Beispiel durchgerechnet

Wir betrachten die Sprache $L = \{\, w \in \{a,b\}^* \mid w \text{ endet auf } ab \,\}$. Ein sehr kompakter NEA hierfür:

Formal: $Z = \{z_0, z_1, z_2\}$, $\Sigma = \{a, b\}$, $S = \{z_0\}$, $E = \{z_2\}$. Übergänge:

Wir prüfen das Wort $w = abab$ per Mengenverfolgung:

Q0 = {z0}
lies a  →  Q1 = δ(z0,a) = {z0, z1}
lies b  →  Q2 = δ(z0,b) ∪ δ(z1,b) = {z0} ∪ {z2} = {z0, z2}
lies a  →  Q3 = δ(z0,a) ∪ δ(z2,a) = {z0, z1} ∪ ∅ = {z0, z1}
lies b  →  Q4 = δ(z0,b) ∪ δ(z1,b) = {z0} ∪ {z2} = {z0, z2}

Q4 ∩ E = {z0, z2} ∩ {z2} = {z2} ≠ ∅   ⇒   w wird akzeptiert.

Der äquivalente DEA per Potenzmengenkonstruktion hat als erreichbare Zustände genau $\{z_0\}$, $\{z_0, z_1\}$ und $\{z_0, z_2\}$ — also drei Zustände, nicht acht. Endzustände sind alle Teilmengen, die $z_2$ enthalten, hier $\{z_0, z_2\}$.

                z0
              /    \
        a:  z0      z1
           /  \       \
     a:  z0   z1   (Sackgasse: δ(z1,a) = ∅)
         |     \
     b:  z0    z2   ← akzeptierender Endzustand
              

Q0 = {z0}
lies 1  →  Q1 = δ(z0,1) = {z0}
lies 0  →  Q2 = δ(z0,0) = {z0, z1}
lies 1  →  Q3 = δ(z0,1) ∪ δ(z1,1) = {z0} ∪ {z2} = {z0, z2}
lies 0  →  Q4 = δ(z0,0) ∪ δ(z2,0) = {z0, z1} ∪ {z3} = {z0, z1, z3}

Q4 ∩ E = {z0, z1, z3} ∩ {z3} = {z3} ≠ ∅   ⇒   w1 akzeptiert.

Q0 = {z0}
lies 1  →  Q1 = {z0}
lies 1  →  Q2 = {z0}
lies 0  →  Q3 = {z0, z1}
lies 0  →  Q4 = δ(z0,0) ∪ δ(z1,0) = {z0, z1} ∪ ∅ = {z0, z1}

Q4 ∩ E = {z0, z1} ∩ {z3} = ∅   ⇒   w2 wird verworfen.

4. Typische Klausurfragen (Lesen!)

Aufgabentyp A — Wort schrittweise durchführen

Ein NEA wird als Zustandsdiagramm oder Übergangstabelle gegeben, ein Wort ist zu prüfen. Verlangt ist ein Berechnungsbaum oder eine Mengenverfolgung. Falle: nicht nur einen Pfad zeichnen und dann behaupten, es sei nicht akzeptiert — Nichtdeterminismus verlangt, dass alle Möglichkeiten mitgeführt werden.

Aufgabentyp B — Sprache eines NEAs bestimmen

Gegeben ist ein NEA, gefragt ist $L(M)$ in beschreibender oder regulärer Form. Man liest die Struktur des Automaten und identifiziert das Muster, das zum Endzustand führen muss. Falle: $\varepsilon$-Kanten übersehen oder mehrere Startzustände ignorieren.

Aufgabentyp C — Potenzmengenkonstruktion durchführen

Gegeben ist ein NEA, gefragt ist der äquivalente DEA. Nur die vom Startzustand tatsächlich erreichbaren Teilmengen aufzeichnen. Falle: alle $2^{|Z|}$ Teilmengen enumerieren — das ist meist unnötig und oft falsch, weil viele Teilmengen unerreichbar sind.

Aufgabentyp D — Argumentieren, warum NEAs nicht mächtiger sind

Gefragt: Zeige, dass zu jedem NEA ein sprachäquivalenter DEA existiert. Antwort: Skizze der Potenzmengenkonstruktion mit dem Argument, dass $\delta'(Q, a) = \bigcup_{q \in Q} \delta(q, a)$ deterministisch ist und $L(M) = L(M')$ per Induktion über die Wortlänge folgt.

5. Fragen zum Selbsttest

6. Dos und Donts in der Klausur