Version vom 11. Februar 2019, 17:08 Uhr

Nichtdeterministische endliche Automaten unterscheiden sich von Deterministischen endlichen Automaten in zwei wesentlichen Punkten:

Die Übergänge zwischen den Zuständen sind nicht eindeutig.
D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.
Ein Wort gilt als akzeptiert, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand gibt.
D.h.: Nicht jeder "Weg" muss zu einem Endzustand führen - es reicht, wenn es einen Weg gibt!
Und der "richtige" Weg ist manchmal ziemlich schwer zu finden...

Beispiel

Der KGB-Automat als Nicht-deterministischer endlicher Automat.

Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.

Man sieht, dass im Zustand q₀ der Übergang für die 0 nicht eindeutig ist; man kann entweder bei q₀ bleiben oder zu q₁ übergehen.

Die Darstellung als Nicht-deterministischer endlicher Automat ist oft viel einfacher als die Darstellung als Deterministischer Endlicher Automat.

Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.
Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren.
- Das Verfahren dazu heißt Potenzmengenkonstruktion und ist reichlich kompliziert, funktioniert aber immer!
  (Das ist mathematisch bewiesen...)

Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine reguläre Grammatik konstruieren:
- Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.
Zu jeder regulären Grammatik lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:
- Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.
- Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der regulären Grammatik zum deterministischen endlichen Automaten.

@@ Zeile 23: / Zeile 23: @@
 =Beziehung zu regulären Grammatiken=
-* Zu jeder [[Reguläre Grammatik|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:
+* '''Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine [[Reguläre Grammatik|reguläre Grammatik]] konstruieren:'''
+** Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.
+* '''Zu jeder [[Reguläre Grammatik|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:'''
 ** Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.
-* Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik|regulären Grammatik]] zum [[Deterministischer Endlicher Automat|deterministischen endlichen Automaten]].
+** Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik|regulären Grammatik]] zum [[Deterministischer Endlicher Automat|deterministischen endlichen Automaten]].