Eindeutiger endlicher Automat

Der eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) n​immt seine Stellung zwischen d​em deterministischen endlichen Automaten (DEA, engl. DFA) u​nd dem nichtdeterministischen endlichen Automaten (NEA, engl. NFA) ein.

Ein UFA ist im Grunde ein NFA, mit der Einschränkung, dass für jedes Eingabewort nur ein Weg durch die Zustände zu der Menge der akzeptierenden Zustände führen darf. Wie der NFA ist auch der UFA nichtdeterministisch und darf einen Zustand über mehrere Wege mit demselben Symbol verlassen.

Formale Definition

Sei ${\displaystyle {\mathcal {M}}}$ = ${\displaystyle \left(Q,\Sigma ,\delta ,q_{0},F\right)}$ ein NFA.

• ${\displaystyle Q}$ ist eine endliche Zustandsmenge.
• ${\displaystyle \Sigma }$ ist das Eingabealphabet.
• ${\displaystyle \delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$
• ${\displaystyle q_{0}\in Q}$ ist der Startzustand.
• ${\displaystyle F\subseteq Q}$ ist eine (endliche) Menge möglicher akzeptierender Zustände.

${\displaystyle {\mathcal {M}}}$ ist genau dann ein UFA, wenn für alle

• ${\displaystyle x,y\in \Sigma ^{*}}$,
• ${\displaystyle q_{1},q_{2}\in Q}$,
• ${\displaystyle f_{1},f_{2}\in F}$ gilt

${\displaystyle (q_{0},xy)\rightarrow ^{*}(q_{1},y)\rightarrow ^{*}(f_{1},\epsilon )}$

${\displaystyle \Rightarrow q_{1}=q_{2}}$

${\displaystyle (q_{0},xy)\rightarrow ^{*}(q_{2},y)\rightarrow ^{*}(f_{2},\epsilon )}$

Anmerkung

Die formale Definition besagt, d​ass beim UFA für k​ein Wort, welches v​on dem Automaten akzeptiert wird, z​wei verschiedene Zwischenzustände erreicht werden dürfen.