Nicht-deterministischer endlicher Automaten: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(Die Seite wurde neu angelegt: „Nichtdeterministische endliche Automaten unterscheiden sich von Deterministischer Endlicher Automat nur in einem wese…“) |
|||
| Zeile 1: | Zeile 1: | ||
Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischen endlichen Automaten | [[Kategorie:endliche Automaten]] | ||
[[Kategorie:Informatik-Q2]] | |||
[[Kategorie:Informatik-Abitur]] | |||
[[Kategorie:Informatik]] | |||
Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischer Endlicher Automat|Deterministischen endlichen Automaten]] nur in einem wesentlichen Punkt: | |||
* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>. | * '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>. | ||
D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben. | D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben. | ||
Version vom 23. Februar 2015, 09:13 Uhr
Nichtdeterministische endliche Automaten unterscheiden sich von Deterministischen endlichen Automaten nur in einem wesentlichen Punkt:
- 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.
Beispiel
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 q0 der Übergang für die 0 nicht eindeutig ist; man kann entweder bei q0 bleiben oder zu q1 übergehen.
Die Darstellung als Nicht-deterministischer endlicher Automat ist oft viel einfacher als die Darstellung als Deterministischer Endlicher Automat.
Beziehung zu deterministischen endlichen Automaten
- 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 ist kompliziert, aber mathematisch bewiesen; Details dazu unter [1]
Beziehung zu regulären Grammatiken
- 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.