Eindeutiger endlicher Automat

Grundidee

Ein eindeutiger endlicher Automat, kurz UFA nach englisch unambiguous finite automaton, ist ein endlicher Automat zwischen dem deterministischen endlichen Automaten (DEA/DFA) und dem nichtdeterministischen endlichen Automaten (NEA/NFA). Er ist im Grunde ein nichtdeterministischer endlicher Automat, aber mit einer wichtigen Einschränkung: Für jedes Eingabewort darf höchstens ein Weg durch die Zustände zu einem akzeptierenden Zustand führen.

Wie ein NFA kann ein UFA nichtdeterministisch sein. Das bedeutet: Von einem Zustand aus können mit demselben Eingabesymbol mehrere mögliche Folgezustände erreichbar sein. Der Unterschied ist, dass diese Mehrdeutigkeit nicht dazu führen darf, dass ein akzeptiertes Wort auf zwei verschiedenen akzeptierenden Wegen verarbeitet werden kann.

Formale Definition

Sei M = (Q, Σ, δ, q0, F) ein NFA. Dabei ist Q eine endliche Zustandsmenge, Σ das Eingabealphabet, δ: Q × Σ → P(Q) die Übergangsfunktion, q0 ∈ Q der Startzustand und F ⊆ Q eine endliche Menge möglicher akzeptierender Zustände.

M ist genau dann ein UFA, wenn für alle x, y ∈ Σ*, q1, q2 ∈ Q und f1, f2 ∈ F gilt: Wenn es einen Lauf (q0, xy) →* (q1, y) →* (f1, ε) gibt und außerdem einen Lauf (q0, xy) →* (q2, y) →* (f2, ε), dann muss q1 = q2 gelten. Hier bedeutet Σ* die Menge aller Wörter über dem Alphabet Σ, P(Q) die Potenzmenge von Q, also die Menge aller Teilmengen von Q, und ε das leere Wort.

Bedeutung der Eindeutigkeit

Die Definition sagt inhaltlich: Bei einem UFA dürfen für kein akzeptiertes Wort zwei verschiedene Zwischenzustände erreicht werden, die beide noch zu einem akzeptierenden Zustand führen. Ein akzeptiertes Wort hat also nur einen akzeptierenden Weg.

Ein UFA kann trotzdem mehrere mögliche Übergänge mit demselben Symbol besitzen. Entscheidend ist nicht, ob der Automat überhaupt verzweigt, sondern ob am Ende für ein akzeptiertes Wort mehr als ein erfolgreicher Weg entsteht. Genau das ist beim UFA ausgeschlossen.