Ein Nicht-Deterministischer endlicher Automat (NEA) ist das Gegenstück zu einem Deterministischen endlichen Automaten. Dabei bedeutet deterministisch, dass für jeden Zustand klar definiert ist, bei welchem Zeichen in welchen Zustand gewechselt wird.
Ein Automat, der nicht deterministisch aufgebaut ist, hat also bei einigen Zuständen für ein Zeichen mehrere Möglichkeiten, in welchen Zustand gewechselt werden muss.
Im obigen Übergangsgraphen ist bim Zustand q1
zu erkennen, dass es zwei Möglichkeiten gibt, mit dem Zeichen a
den Zustand zu wechseln. Daher wird der Automat als nicht-deterministisch betrachtet. Bei der Wahl des richtigen “Weges” kommt es darauf an, mit welchen Weg man am Ende einem Zielzustand näher ist.
Umwandlung eines NEA in einen DEA - Potenzmengekonstruktion
Zu jedem nichtdeterministischen endlichen Automaten A (mit n Zuständen) gibt es einen deterministischen endlichen Automaten A’ mit maximal Zuständen.
a | b | |
---|---|---|
Senke | ||
Senke | ||
Senke | Senke |
Um eine NEA in einen DEA umzuwandeln wird für den NEA eine Übergangsfunktion erstellt. Dabei werden bei Übergängen, die nicht deterministisch sind, neue Zustände erstellt. Diese fassen jeweils alle Zustände zusammen, die mit einem Zeichen von einem bestimmten Zustand aus erreicht werden können. In unserem Beispiel kann aus dem Zustand q1
sowohl q3
, als auch q2
mit einem a
erreicht werden. Daher wird der neue Zustand q23
erstellt.
Für diese neuen Zustände wird dann auch geschaut, welche Zustände erreicht werden können. Für den neuen Zustand q23
ist eine Übergangsfunktion bei einem a
nur für den Zustand q3
definiert. Sie zeigt auf den den Zustand q3
. Also wird q3
als Ziel bei einem a
als Zeichen definiert.
Würde nun beispielsweise auch der Zustand q2
mit einem a
auf den Zustand q1
zeigen, müsste ein neuer Zustand definiert werden, nämlich q13
, da mit dem Zustand q23
sowohl q1
, als auch q2
erreicht werden kann.
Die Übergangsfunktion ist dann fertiggestellt, wenn keine undefinierten Zustände in der Tabelle mehr vorhanden sind. Jeder Zustand, der eine Zahl eines Endzustandes in sich hat, wird dann zu einem Endzustand.