Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen beispielsweise Einzelnachweisen ausgestattet Angaben ohne ausreichenden Beleg konnten demnachst entfernt werden Bitte hilf Wikipedia indem du die Angaben recherchierst und gute Belege einfugst Der eindeutige endliche Automat englisch unambiguous finite automaton UFA nimmt seine Stellung zwischen dem deterministischen endlichen Automaten DEA engl DFA und dem nichtdeterministischen endlichen Automaten NEA engl NFA ein Ein UFA ist im Grunde ein NFA mit der Einschrankung dass fur jedes Eingabewort nur ein Weg durch die Zustande zu der Menge der akzeptierenden Zustande fuhren darf Wie der NFA ist auch der UFA nichtdeterministisch und darf einen Zustand uber mehrere Wege mit demselben Symbol verlassen Formale Definition BearbeitenSei M displaystyle mathcal M nbsp Q S d q 0 F displaystyle left Q Sigma delta q 0 F right nbsp ein NFA Q displaystyle Q nbsp ist eine endliche Zustandsmenge S displaystyle Sigma nbsp ist das Eingabealphabet d Q S P Q displaystyle delta Q times Sigma rightarrow mathcal P Q nbsp q 0 Q displaystyle q 0 in Q nbsp ist der Startzustand F Q displaystyle F subseteq Q nbsp ist eine endliche Menge moglicher akzeptierender Zustande M displaystyle mathcal M nbsp ist genau dann ein UFA wenn fur alle x y S displaystyle x y in Sigma nbsp q 1 q 2 Q displaystyle q 1 q 2 in Q nbsp f 1 f 2 F displaystyle f 1 f 2 in F nbsp gilt q 0 x y q 1 y f 1 ϵ displaystyle q 0 xy rightarrow q 1 y rightarrow f 1 epsilon nbsp q 1 q 2 displaystyle Rightarrow q 1 q 2 nbsp dd dd dd dd dd dd dd dd dd dd q 0 x y q 2 y f 2 ϵ displaystyle q 0 xy rightarrow q 2 y rightarrow f 2 epsilon nbsp dd Anmerkung Bearbeiten Die formale Definition besagt dass beim UFA fur kein Wort welches von dem Automaten akzeptiert wird zwei verschiedene Zwischenzustande erreicht werden durfen Abgerufen von https de wikipedia org w index php title Eindeutiger endlicher Automat amp oldid 230850686
