Nichtdetirministische, endliche Zustandsautomaten (NEA)


(SkriptAtfsEckNr1, S. 19)

1. Unterschied zum DetEndlAutomaten DEA

  • 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)



2. Beispiel


Ein nichtdeterministischer, endlicher Automat soll die Folge SOS erkennen.


image


Test mit der Folge ASOOSSOS


image


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
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki