=====Nichtdetirministische, endliche Zustandsautomaten (NEA)=====

(SkriptAtfsEckNr1, S. 19)

==a==Unterschied zum [[DetEndlAutomaten DEA]]==a==

~-Ein NEA kann mehr als einen Anfangszustand erhalten

~-Nicht in jeden Zustand ist zu jeden Eingabesymbol ein Übergang definiert (kein Folgezustand)

~-Es kann Zustände geben, die für ein und dasselbe Eingabesymbol mehr als einen Folgezustand besitzen (eine Folgezustandmenge)



==a==Beispiel==a==

Ein nichtdeterministischer, endlicher Automat soll die Folge SOS erkennen.


{{image url="images/ATFS_NEA.png"}}


Test mit der Folge ASOOSSOS


{{image url="images/ATFS_NEA_Auswert.png"}}


Das Diagramm zeigt den Verlauf der Zustände und die noch verbleibenden Zeichen der Folge an. Wie man gut erkennen kann nimmt der NEA gelegentlich zwei Zustände gleichzeitig an und verwirft auch Zustände, wenn sie in einer Sackgasse (orange markiert) enden.


----
Siehe auch {{backlinks}}