Dieses Thema ist für Abiturienten im Fach Informatik von besonderem Interesse. Für den Abiturjahrgang 2019 schreiben die Vorgaben des Landes NRW das Thema "nichtdeterminierte endliche Automaten" vor. Daher habe ich spontan diese Seite über NDEAs bzw. nichtdeterminierte endliche Automaten geschrieben.
Definition
Nichtdeterminierter endlicher Automat (NDEA oder auch NEA)
Ein nichtdeterminierter endlicher Automat (DEA) ist ein 5-Tupel A = (Q, S, δ, q0, F) mit
- Q = endliche Menge von Zuständen
- S = Eingabealphabet
- δ = Übergangsfunktion
- q0 = Startzustand
- F = endliche Menge von Endzuständen.
Auf den ersten Blick sieht diese Definition genau so aus wie die Definition eines determinierten endlichen Automaten. Auf den zweiten Blick auch. Das liegt daran, dass die Definition keine näheren Angaben macht, wie die Übergangsfunktion auszusehen hat.
Bei einem DEA weist die Übergangsfunktion jedem Zustand und jedem Eingabezeichen genau einen Folgezustand zu. Bei einem NDEA ist das etwas anders. Hier kann die Übergangsfunktion einem Zustand und einem Eingabezeichen mehr als einen Folgezustand zuweisen. Schauen wir uns das mal konkret an einem einfachen Beispiel an:
Ein nichtdeterminierter endlicher Automat mit drei Zuständen
Aus dem Startzustand 1 gelangt man mit dem Zeichen 'a' in den Zustand 2.
Ist der Automat im Zustand 2, so gelangt man mit dem Eingabezeichen 'b' gleichzeitig in den Zustand 2 und 3. Das ist so ähnlich wie die Sache mit Schrödingers Katze. Wenn sich der Automat im Zustand 2 befindet und dann das Zeichen 'b' kommt, kann man nicht sehen, in welchem Folgezustand sich der Automat befindet. Er könnte sich noch im Zustand 2 befinden, aber auch schon im Zustand 3.
Der Vergleich mit Schrödingers Katze hinkt allerdings etwas, denn der Benutzer des Automaten kann ja in den Automaten hineinschauen und dann den Weg wählen, der ihm am geeignetsten erscheint. Aber im Gegensatz zum DEA stehen beim NDEA (oder NEA) oft mehrere alternative Wege zur Verfügung.
Wir wollen diesen NDEA nun formal definieren (so etwas wird auch immer wieder in den Abituraufgaben verlangt).
Zustandsmenge Q
Q = {1, 2, 3}
Eingabealphabet S
S = {a, b}
Übergangsfunktion δ
siehe Abbildung 1
Startzustand q0
q0 = 1
Endzustände F
F = {3}
Umwandlung eines NDEA in einen DEA
Um einen DEA in einen äquivalenten NDEA (oder NEA) zu konvertieren, verfährt man nach dem Prinzip der Potenzmengenkonstruktion.
| Zustand | Eingabesymbol a | Eingabesymbol b |
| {1} | {2} | --- |
| {2} | {2} | {2,3} |
| {2,3} | {2} | {2,3} |
Bei dieser Potenzmengenkonstruktion beginnt man mit dem Startzustand und überlegt, in welchen Zustand / welche Zustände man mit dem Eingabesymbol a gelangt. Hier ist die Sache noch eindeutig; vom Startzustand 1 gelangt man mit a direkt in den Zustand 2.
Beim Zustand 2 sieht die Sache schon anders aus. Mit dem Eingabesymbol a bleibt man im Zustand 2, aber mit dem Eingabesymbol b kann man entweder in 2 verbleiben oder in Zustand 3 gelangen. Schrödinger-Fans würden jetzt sagen, man gelangt mit b gleichzeitig in Zustand 2 und 3 bzw. man kann nicht entscheiden, ob man sich in Zustand 2 oder 3 befindet.
Die Zustände 2 und 3 werden daher als Zustandsmenge {2,3} zusammengefasst und dann formal wieder wie ein Zustand behandelt, was die letzte Zeile der Tabelle erklärt.
Aus der Zustandsmenge {2,3} kommt man mit dem Eingabesymbol a wieder in den Zustand 2. Mit dem Eingabesymbol b kommt man wieder zurück in die Zustandsmenge {2,3}.
Diese Tabelle können wir nun wieder als Übergangsfunktion eines determinierten endlichen Automaten ansehen und graphisch darstellen:
Der äquivalente DEA
Jede Zustandsmenge, die einen der Endzustände des NDEA enthält, ist auch jetzt ein Endzustand. Das gilt hier für die Zustandsmenge {0,2}.
Ein weiteres Beispiel
Betrachten Sie nun folgenden NEA, der alle Ziffernfolgen akzeptiert, die auf 007 enden. Die Idee zu diesem DEA kommt natürlich wieder aus einer alten NRW-Abituraufgabe.
Ein NEA, der Ziffernfolgen erkennt, die auf 007 enden.
Beginnen wir gleich mit der Konstruktion der Teilmengen bzw. "Superzustände". Es ergibt sich damit folgende Tabelle:
| Zustand | 1,2,3,4,5,6, 8,9 | Eingabesymbol 0 | Eingabesymbol 7 |
| {1} | {1} | {1, 2} | {1} |
| {1, 2} | {1} | {1, 3} | {1} |
| {1, 3} | {1} | {1, 2} | {1, 4} |
| {1, 4} | {1} | {1, 2} | {1} |
Bei dieser Tabellenkonstruktion muss man sich ziemlich konzentrieren, Fehler werden hier ganz schnell gemacht, wenn man nicht aufpasst. Setzen wir diese Tabelle nun wieder in eine Graphik um.
Der äquivalente DEA
Die Zahl der Zustände hat sich gegenüber dem NEA nicht vergrößert, wohl aber die Zahl der Übergänge. Wir wollen nun anhand einiger Beispiele testen, ob der DEA tatsächlich nur Ziffernfolgen akzeptiert, die auf 007 enden.
Probieren wir zunächst einmal - ganz radikal - die Ziffernfolge 007, die ja auch auf 007 endet. Mit der 0 gelangen wir von Zustand 0 in den Zustand {0,1}, mit der zweiten 0 in den Zustand {0,2} und mit der 7 in den Endzustand 3. Die Ziffernfolge 007 wird also von dem Automaten akzeptiert.
Nun denken wir uns mal eine beliebige auf 007 endende Ziffernfolge aus, beispielsweise 1436237400752007.
Das ist jetzt eine ziemlich lange "zufällige" Ziffernfolge. Mit den ersten acht Ziffern 14362374 bleiben wir stets im Zustand 0. Dann kommt die erste 0, die uns in den Zustand {0,1} führt. Mit der zweiten 0 geht es in den Zustand {0,2} und mit der 7 in den Zustand {0,3}. Dann kommen aber weitere Ziffern. Die 5 bringt uns in den Zustand 0, mit der 2 bleiben wir in Zustand 0. Nun kommt wieder die Ziffernfolge 007, die uns in den Endzustand {0,3} bringt. Die Ziffernfolge ist fertig abgearbeitet, der DEA befindet sich in einem Endzustand, also gilt die Ziffernfolge als akzeptiert.
Sinn und Nutzen von NEAs
Einen DEA kann man direkt in eine Tabelle umsetzen und diese dann leicht implementieren, so dass man eine Methode schreiben kann, die einen DEA simuliert. Bei einem NEA geht das nicht, weil sich ein NEA gleichzeitig in mehreren Zuständen befinden kann. Warum beschäftigt man sich dann überhaupt mit NEAs?
Wie wir bei unseren beiden Beispielen gesehen haben, ist ein NEA wesentlich einfacher aufgebaut als ein äquivalenter DEA. "Äquivalenz" heißt hier, dass der DEA die gleiche Sprache hat wie der NEA. Einen NEA kann man schneller und einfacher konstruieren als den äquivalenten DEA. Hat man einen NEA konstruiert, kann mit Hilfe des hier vorgestellten Teilmengen-Algorithmus leicht ein äquivalenter DEA konstruiert werden, den man dann wieder leicht implementieren kann.
Ein NEA im Abitur 2019 (NRW)
Die Informatik-Abituraufgabe HT3 von 2019 (NRW) enthielt die Aufgabe, aus einen NEA einen äquivalenten DEA zu konstruieren.
Der NEA aus dem Abitur NRW 2019
Die Schüler sollten in den ersten (leichten) Aufgaben diesen Automaten formal beschreiben und als nicht-deterministischen endlichen Automaten erkennen, zum Beispiel indem sie angaben, dass man mit einen z (für Ziffer) aus dem Zustand q1 gleichzeitig in die Zustände q3 und q4 gelangt.
Die Hauptaufgabe war dann aber die Umwandlung des NEAs in einen äquivalenten DEA. Vielleicht gibt es hier ja irgendeinen Trick, den ich noch nicht kenne, aber die Anwendung des Teilmengen-Verfahrens in der Klausur war ganz schön anspruchsvoll.
Fangen wir einfach mal an. Welche Eingabesymbole gibt es? Diese Frage ist für die Konstruktion der Tabelle mit der Übergangsfunktion wichtig. Das Ergebnis ist diese Menge: {m, z, 0, -, /}. Damit können wir jetzt unsere Tabelle konstruieren:
| Zustand | m | z | 0 | - | / |
| {q0} | {q1} |
Den ersten Zustand q0 haben wir damit abgearbeitet. Dabei haben wir einen neuen Zustand bzw. eine neue Zustandsmenge {q1} "produziert", die aber aus nur einem Zustand besteht (und dann trotzdem eine Menge ist).
Kümmern wir uns jetzt um die neue "Menge" {q1}:
| Zustand | m | z | 0 | - | / |
| {q1} | {q3,q4} | {q4} | {q2} |
Jetzt haben wir drei neue Zustandsmengen "produziert", um die wir uns kümmern müssen:
| Zustand | m | z | 0 | - | / |
| {q3,q4} | {q4} | {q4} | {q5} | ||
| {q4} | {q5} | ||||
| {q2} | {q3,q4} |
Und wieder ist eine neue Zustandsmenge entstanden, nämlich {q5}. Was passiert, wenn wir uns im Zustand q5 befinden?
| Zustand | m | z | 0 | - | / |
| {q5} | {q7,q8} | {q8} | {q6} |
Jetzt haben wir drei neue Zustandsmengen, {q7,q8}, {q8}und {q6}:
| Zustand | m | z | 0 | - | / |
| {q7,q8} | {q8} | {q8} | |||
| {q8} | |||||
| {q6} | {q7,q8} |
Die graphische Darstellung der so erhaltenen Übergangsfunktion des äquivalenten deterministischen Automaten sieht so aus:
Die äquivalente deterministische endliche Automat
Anmerkung 1:
Das ist übrigens das erste Mal gewesen, dass im Zentralabitur NRW von den Schülern verlangt wurde, einen NDEA in einen DEA zu verwandeln.
Anmerkung 2:
Das war natürlich nicht die vollständige Abituraufgabe, sondern nur ein Teil davon. Im weiteren Teil sollten die Schüler(innen) diesen Automaten nach bestimmten Vorgaben ergänzen und dann auch noch in eine entsprechende reguläre Grammatik verwandeln.
Anmerkung 3:
Diese Aufgabe ist nicht gut! Erstens ist der NEA viel zu kompliziert für eine Abituraufgabe, er hat zu viele Zustände. Und zweitens ist der resultierende äquivalente DEA genau so komplex wie der NEA; die Vorteile von NEAs gegenüber DEAs werden bei dieser Aufgabe überhaupt nicht deutlich.
Anmerkung 4:
Der Zustand 7 ist jetzt ein Endzustand. Das hatte ich in der ursprünglichen Version dieser Graphik übersehen. Frau Weber von der Hochschule Koblenz hat mich dankenswerterweise auf diesen Fehler aufmerksam gemacht.