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.
