Das Kefk Network Wiki befindet sich im Testbetrieb.

Eindeutiger endlicher Automat

Aus Kefk.

Wechseln zu: Navigation, Suche

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 \mathcal{M} = \left( Q, \Sigma, \delta, q_0, F \right) ein NFA.

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


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

  • x,y \in \Sigma^*,
  • q_1, q_2 \in Q,
  • f_1, f_2 \in F gilt
(q_0,xy) \rightarrow^* (q_1,y) \rightarrow^* (f_1,\epsilon)
\Rightarrow q_1 = q_2
(q_0,xy) \rightarrow^* (q_2,y) \rightarrow^* (f_2,\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.

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Eindeutiger_endlicher_Automat, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Eindeutiger_endlicher_Automat“
Persönliche Werkzeuge