Nichtdeterministische Automaten

Ein nichtdeterministischer endlicher Automat (NEA, englisch NFA) erlaubt im Gegensatz zum DEA mehrere oder gar keine Folgezustände pro Eingabesymbol. Beim Lesen eines Zeichens kann der Automat „raten“, welchen Übergang er nimmt. Ein Wort wird akzeptiert, wenn mindestens ein Berechnungspfad in einem Endzustand endet.

Ein NEA ist ein 5-Tupel \( N = (Q, \Sigma, \delta, q_0, F) \) mit:

• \( \delta : Q \times \Sigma \rightarrow \mathcal{P}(Q) \)

– die Überführungsfunktion liefert eine Menge von Folgezuständen (möglicherweise leer, einer oder viele). Manche Definitionen erlauben zusätzlich \( \varepsilon \)-Übergänge, also Zustandsübergänge ohne Lesen eines Zeichens.

Bemerkenswert: NEA und DEA erkennen genau dieselbe Sprachklasse – die regulären Sprachen. Der NEA ist also nicht mächtiger, aber oft kleiner und einfacher zu konstruieren. Beispiel: Für die Sprache „alle Wörter, deren drittletztes Zeichen ein a ist“ benötigt ein DEA acht Zustände, ein NEA nur vier.

Jeder NEA kann in einen äquivalenten DEA umgewandelt werden. Das Verfahren heißt Potenzmengenkonstruktion (Subset Construction):

1. Die Zustände des neuen DEA sind Teilmengen der Zustände des NEA.
2. Startzustand des DEA ist die einelementige Menge \( \{q_0\} \) (bzw. \( \varepsilon \)-Abschluss).
3. Für jeden DEA-Zustand \( S \) und jedes Eingabezeichen \( a \) ist der Folgezustand die Vereinigung aller \( \delta(q, a) \) für \( q \in S \).
4. Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten.

Im schlimmsten Fall hat der entstehende DEA \( 2^{|Q|} \) Zustände – die Konstruktion ist also möglich, aber kann teuer sein.

NEA über \( \Sigma = \{a, b\} \) für Wörter, die auf ab enden: drei Zustände \( q_0, q_1, q_2 \).

      | a       | b
------+---------+--------
 q0   | {q0,q1} | {q0}
 q1   | {}      | {q2}
 q2   | {}      | {}      (Endzustand)

Im Zustand \( q_0 \) hat der Automat bei a die Wahl: bleiben oder zu \( q_1 \) wechseln. Erst der Pfad, der das letzte a „richtig“ rät, akzeptiert.

NEAs sind die natürliche Zwischenstufe zwischen regulären Ausdrücken und implementierten DEAs. Tools wie grep oder die Java-Klasse Pattern übersetzen einen regulären Ausdruck zunächst in einen NEA und dann (bei Bedarf) in einen DEA. Die Konstruktion folgt dem Algorithmus von Thompson.

Verwechslung der Äquivalenz: NEA und DEA erkennen dieselben Sprachen, sind aber verschieden aufgebaut. Beim Potenzmengenverfahren werden nicht alle erreichbaren Teilmengen aufgelistet oder leere Mengen vergessen. Bei \( \varepsilon \)-Übergängen wird der \( \varepsilon \)-Abschluss vergessen.

Zusammenfassung: NEAs erlauben mehrere Folgezustände und akzeptieren, sobald ein Pfad zum Erfolg führt. Sie sind genauso mächtig wie DEAs und lassen sich per Potenzmengenkonstruktion in DEAs umwandeln.

Abitur-Tipp: Übe die Potenzmengenkonstruktion an einem kleinen NEA mit drei Zuständen – das ist eine klassische Prüfungsaufgabe.