L = { w | w endet mit 01 }
q0 hat mehrere Ausgänge für 0
q1 hat einen Ausgang für 1, aber keinen für 0, d.h. 0 schlägt fehl
q2 hat keine Ausgänge, d.h. q2 akzeptiert keine weiteren Eingaben
Vorteil: NFA ist oft intuitiver zu entwickeln
Definition – Nichtdeterministischer endlicher Automat
Ein nichtdeterministischer endlicher Automat (non-deterministic finite
automaton or NFA)
ist ein 5-Tupel A = (Q, Σ, δ, q0, F) mit
• Q: endliche Menge von Zuständen (states)
• Σ: ein Alphabet
• δ: eine Übergangsfunktion (transition function) mit δ : (Q × Σ) → 2^Q
(2^Q ist die Menge aller Teilmengen von Q)
• q0 : der Startzustand (start state) aus Q
• F: Menge der Endzustände (final states or accept states) mit F⊆Q
Definition – Erweiterte Übergangsfunktion für NFA
Die erweiterte Übergangsfunktion (extended transition function) ˆδ für einen
NFA wird definiert als:
Induktionsbeginn: ˆδ(q, ε) = {q}.
Induktionsschritt: Sei w = xa, d.h. a ist das letzte Zeichen des Wortes
w ∈ Σ∗
und gelte ˆδ(q, x) = {p1, p2, . . . , pk}.
Dann gilt: δˆ(q, w) = δ(ˆδ(q, x), a) = δ(p1, a) ∪ δ(p2, a) ∪ · · · ∪
δ(pk, a).
Hinweis bei DFA :Wenn laut die Sprache Null akzeptiert
bedeutet nicht dass Ziffern 0 akzeptiert sondern leeres Wort akzeptiert.
Definition – Vom NFA akzeptierte Sprache
A = (Q, Σ, δ, q0, F)
vom NFA A akzeptierte Sprache L(A)ist definiert als:
L(A) = { w ∈ Σ∗ | ˆδ(q0, w) ∩ F ̸= ∅ }.
D.h. w ist in L(A), wenn ˆδ(q0, w) mindestens einen
Endzustand enthält.
Verfahren – NFA → DFA mit Teilmengenkonstruktion (subset construction)
Konstruiere DFA D aus NFA N = (QN, Σ, δN, q0, FN) wie folgt:
DFA D = (QD, Σ, δD, {q0}, FD)
QD Menge aller Teilmengen von QN
FD Menge aller Teilmengen S von QN mit S ∩ FN ̸= ∅.
nur die einem Endzustand enthält (S ist Selektion)
Für jedes S ⊆ QN und a ∈ Σ gilt:
δD(S, a) = ∪p∈SδN(p, a)
Die geschweifte Klammer sind hier keine Mengen
sondern Namen der Zuständen von neuen DFA
Verfahren NFA → DFA abwartende Auswertung(lazy evaluation)
Induktionsanfang: {q0} ist erreichbar.
Induktionsschritt:
Zustand S ∈ DFA mit S ⊆ QN erreichbar
dann alle a ∈ Σ die Zustände δD(S, a) erreichbar.
Theorem – Äquivalenz NFA–DFA durch Teilmengenkonstruktion
DFA D = (QD, Σ, δD, {q0}, FD) der zu gegebenem
NFA N = (QN, Σ, δN, q0, FN)
durch die Teilmengenkonstruktion generiert
wurde, dann gilt L(D) = L(N).
Beweis-Skizze: durch vollständige Induktion über die Länge
der Wörter
Eine Sprache L wird durch einen DFA akzeptiert genau dann, wenn L durch einen
NFA akzeptiert wird.
DFA ⇐ NFA: Theorem NFA → DFA
DFA ⇒ NFA: klar, da jeder DFA auch ein NFA ist
Textsuche ist eine praktische Anwendung von endlichen Automaten
Verfahren – Konstruktion NFA zur Textsuche
Automat
k + 1 Zustände:
q0 den Startzustand
weitere Zustände q1, . . . , qk,
folgende Übergänge
δ(q0, a) = q0 für a ∈ Σ und
δ(qi−1, ai) = qi für i = 1, . . . , k.
Der Endzustand sei qk.
Für mehrere Worte füge entsprechende weitere Zustände ein.