Nichtdeterministischer Automat
Du willst wissen, was ein nichtdeterministischer Automat in der theoretischen Informatik ist? In diesem Beitrag zeigen wir dir ein einfaches Beispiel und erklären dir den Unterschied zwischen deterministischen und nichtdeterministischen endlichen Automaten. Zusätzlich findest du hier alle wichtigen Besonderheiten zur Spracherkennung und Epsilon-Übergängen.
Inhaltsübersicht
Definition
Ein nichtdeterministischer endlicher Automat – kurz NEA (Informatik) oder auf Englisch „nondeterministic finite automaton“ kurz NFA genannt – gehört in der Informatik zu den endlichen Automaten.
Im Unterschied zum DEA sind die Übergangsrelationen der Zustände beim NEA nicht eindeutig. Das bedeutet, dass es bei gleichen Bedingungen oft mehrere Folgezustände auf einen Zustand gibt, und nicht genau definiert ist, welcher genutzt wird.
Nichtdeterministischer endlicher Automat – Beispiel
Als Einstieg schauen wir uns das Ganze doch einfach mal an. Ein nichtdeterministischer endlicher Automat als Beispiel könnte wie folgt aussehen:
Dass z0 der Startzustand und z1 der Endzustand des Automaten ist, solltest du ohne Probleme erkennen können. Wenn nicht, schaust du dir am besten unser Video zu endlichen Automaten an.
Wenn du nun die Zahlen „0 1 1“ in den Automaten eingeben möchtest, wirst du schon an der zweiten Stelle des Wortes feststellen, dass es mehr als eine Möglichkeit als Zustandsübergang gibt. Komisch, oder?
Unterschied deterministischer/ nichtdeterministischer Automat
Genau darin liegt der wichtigste Unterschied zwischen deterministischen und nichtdeterministischen Automaten. Um das zu verdeutlichen, schauen wir uns eine Gegenüberstellung der zwei Varianten an. Beide Automaten erkennen Eingaben, die mit „d“ beginnen und mit null bis n mal „u“ beziehungsweise „a“ enden. Die beiden Automaten sind also äquivalent.
Bestimmt ist dir schnell aufgefallen, dass der NEA kleiner ist als der DEA. Nimm jedoch nicht einfach an, dass ein nichtdeterministischer endlicher Automat dadurch auch einfacher ist! Anders als beim DEA ist hier nicht immer eindeutig, welcher Zustand der richtige beziehungsweise sinnvollste Folgezustand für die aktuelle Eingabe ist. Doch warum ist das wichtig? Stell dir vor, du liest das Wort „du“ ein, und entscheidest dich im NEA für den oberen Weg. Das nun folgende „u“ kann dort nicht eingelesen werden. Genau das darf aber nicht passieren!
Ein weiterer wichtiger Unterschied zwischen NEA und DEA ist, dass ein nichtdeterministischer endlicher Automat mehrere Startzustände geben kann. Beim DEA ist dieser immer eindeutig!
Formale Definition – Nichtdeterministischer endlicher Automat
Wie können wir einen solchen Automaten nun formal definieren? Hierfür reicht uns ein Tupel aus fünf Elementen:
N = (Z, E, δ, Zstart, Zend)
- Z ist die endliche Menge von Zuständen,
- E das Alphabet von Eingabesymbolen
- und δ die Übergangsrelation. (Diese ist beim NEA keine Übergangsfunktion, da es für gleiche Ausgangssituationen mehrere Folgezustände geben kann.)
- Zstart und Zend sind jeweils die Mengen der Start- beziehungsweise Endzustände.
Schauen wir uns das Ganze am Beispiel vom Beginn des Videos an.
Die Menge der Zustände besteht hierbei aus z0 und z1.
Das Eingabealphabet setzt sich aus den Buchstaben 0 und 1 zusammen: E = {0, 1}
Kommen wir zur Übergangsrelation. Diese wird als die Menge aller möglichen Zustandsübergänge dargestellt, wobei jeweils zuerst der alte Zustand z, die Eingabe 0 und der neue Zustand z‘ genannt werden. In diesem Beispiel gibt es nur drei Zustandsübergänge. Das sieht dann so aus: δ = {(z0, 0, z0), (z0, 1, z0), (z0, 1, z1)}. Nun muss nur noch z0 in Zstart und z1 in Zend eingefügt werden und der Automat ist fertig definiert.
Zustandsgraph
Versuchen wir das Ganze nun in die andere Richtung. Gegeben sei folgender Automat:
Z = {z0, z1, z2, z3}
E = {„x“, „y“}
δ = { (z0, „x“, z1), (z1, „x“, z1), (z1, „y“, z1), (z1, „y“, z2), (z3, „y“, z1)}
Zstart = {z0, z3}
Zend = {z2}
Lass uns diesen Automaten nun Schritt für Schritt als Zustandsgraph darstellen:
Als erstes übernehmen wir die vier Zustände. Nun markieren wir alle Startzustände aus Zstart mit einem Pfeil und alle Endzustände aus Zend mit einer weiteren Umkreisung. Zu guter Letzt fügen wir noch die Zustandsübergänge hinzu. Hierfür gehen wir Element für Element durch die Menge δ und zeichnen die jeweiligen Übergänge ein. Fertig!
Besonderheiten – Nichtdeterministischer Automat
Ein nichtdeterministischer endlicher Automat hat eine wichtige Besonderheit, wenn es um das Durchlaufen des Automaten geht. Denn da ist nicht immer jeder Schritt eindeutig! Es muss also entweder der Automat entscheiden, welchen Zustand er bei mehreren möglichen Folgezuständen annimmt oder es müssen entsprechend viele Kopien des Automaten erstellt werden, wobei jede Kopie einen anderen Folgezustand wählt.
Da wir dieses Problem beim DEA nicht haben, wird oft nach einer Umformung vom NEA zum DEA gefragt. Dies funktioniert zum Beispiel mit der sogenannten Potenzmengenkonstruktion , über die du in diesem Video mehr erfahren kannst.
Spracherkennung
Die Spracherkennung ist der Funktionsweise des deterministischen endlichen Automaten sehr ähnlich. Du musst hierbei lediglich beachten, dass alle möglichen Zustandsübergänge für eine Eingabe durchgeführt werden müssen. Sobald nach dem Einlesen des gesamten Eingabeworts ein Endzustand erzielt werden kann, gilt die Eingabe als erfolgreich, ansonsten aber als nicht akzeptiert.
Epsilon-Übergänge
Eine eigentlich simple aber wirksame Komponente eines nichtdeterministischen endlichen Automaten sind die Epsilon-Übergänge. Diese sind Zustandsübergänge ohne Eingabe. Das heißt, sie können bei Bedarf vor oder nach dem Einlesen eines Zeichens auftreten.
Zu jedem NEA mit Epsilon-Übergängen existiert einer ohne diese Übergänge und umgekehrt. Um das zu veranschaulichen, vergleichen wir einen NEA ohne Epsilon-Übergänge mit einem NEA, der Epsilon-Übergänge verwendet.
Beide Automaten akzeptieren Eingaben, bei denen zuerst null bis n mal „x“ vorkommt und daraufhin dasselbe zuerst mit „y“ und dann mit „z“. Beim Epsilon-NEA wird dies dadurch erreicht, dass vor Einlesen eines Zeichens direkt gesprungen werden kann. Beginnt ein Wort mit „y“, so kann der Automat, bevor er das „y“ einliest, direkt von z0 zu z1 springen.
Du siehst sofort, dass der Automat mit Epsilon-Übergängen dadurch deutlich kompakter und leichter zu verstehen ist als der ohne.
Nun hast du einen Überblick über alle wichtigen Faktoren. Ein nichtdeterministischer Automat ist doch gar nicht so schwer zu verstehen, oder?