Theoretische Informatik

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:

Nichtdeterministischer Automat, Nichtdeterministischer endlicher Automat, NEA
direkt ins Video springen
Nichtdeterministischer Automat

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.

Unterschied deterministischer nichtdeterministischer Automat, Unterschied NEA DEA
direkt ins Video springen
Unterschied deterministischer/nichtdeterministischer Automat

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}

Übergangsrelation - Formale Definition
direkt ins Video springen
Übergangsrelation

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:

Zustandsgraph NEA
direkt ins Video springen
Zustandsgraph NEA

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.

Epsilon Übergänge Vergleich
direkt ins Video springen
Epsilon Übergänge

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?

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.