imported>Neutronstar2 am 13. Februar 2023 um 13:39 Uhr

2023-02-13T13:39:19Z

Neue Seite

{{Belege}}
Der '''eindeutige endliche Automat''' ({{enS|''unambiguous finite automaton''}}, ''UFA'') nimmt seine Stellung zwischen dem ''deterministischen'' endlichen Automaten ([[Deterministischer endlicher Automat|DEA]], engl. DFA) und dem ''nichtdeterministischen'' endlichen Automaten ([[Nichtdeterministischer endlicher Automat|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 <math>\mathcal{M}</math> = <math>\left( Q, \Sigma, \delta, q_0, F \right)</math> ein NFA.

:*<math>Q</math> ist eine endliche Zustandsmenge.
:*<math>\Sigma</math> ist das Eingabealphabet.
:*<math>\delta : Q \times \Sigma \rightarrow \mathcal{P}(Q)</math>
:*<math>q_0 \in Q</math> ist der Startzustand.
:*<math>F \subseteq Q</math> ist eine (endliche) Menge möglicher akzeptierender Zustände.

<math>\mathcal{M}</math> ist genau dann ein UFA, wenn für alle
:*<math>x,y \in \Sigma^*</math>,
:*<math>q_1, q_2 \in Q</math>,
:*<math>f_1, f_2 \in F</math> gilt

::<math>(q_0,xy) \rightarrow^* (q_1,y) \rightarrow^* (f_1,\epsilon)</math>
::::::::::::<math>\Rightarrow q_1 = q_2</math>
::<math>(q_0,xy) \rightarrow^* (q_2,y) \rightarrow^* (f_2,\epsilon)</math>

=== 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.

[[Kategorie:Automatentheorie]]

Eindeutiger endlicher Automat - Versionsgeschichte

imported>Neutronstar2 am 13. Februar 2023 um 13:39 Uhr