Der eindeutige endliche Automat (UFA = unambiguous finite automaton) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DFA) und dem nichtdeterministischen endlichen Automaten (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 beim NFA, ist auch der UFA nichtdeterministisch und darf einen Zustand über mehrere Wege mit demselben Symbol verlassen.

Formale Definition

---

Sei $\backslash mathcal\{M\}$ = $\backslash left(\; Q,\; \backslash Sigma,\; \backslash delta,\; q\_0,\; F\; \backslash right)$ ein NFA.

• $Q$ ist eine endliche Zustandsmenge.

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

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

• $x,y\; \backslash in\; \backslash Sigma^*$,

• $q\_1,\; q\_2\; \backslash in\; Q$,
• $f\_1,\; f\_2\; \backslash in\; F$ gilt

$(q\_0,xy)\; \backslash rightarrow^*\; (q\_1,y)\; \backslash rightarrow^*\; (f\_1,\backslash epsilon)$

$\backslash Rightarrow\; q\_1\; =\; q\_2$

$(q\_0,xy)\; \backslash rightarrow^*\; (q\_2,y)\; \backslash rightarrow^*\; (f\_2,\backslash epsilon)$

Anmerkung

Die formale Definition besagt, dass beim UFA für kein Wort, welches von dem Automaten akzeptiert wird, zwei verschiedene Zwischenzustände erreicht werden dürfen.

Automatentheorie