Folge 26 - Theorieteil: NDEAs

1. Ein Beispiel

Erinnern Sie sich noch an das rekursive Einfügen von neuen Elementen in einen binären Suchbaum. Der rekursive Algorithmus ist extrem kurz im Vergleich zu einem nicht-rekursiven Algorithmus. Auch das rekursive Durchsuchen bzw. die rekursive Ausgabe des Binärbaums ist wesentlich einfacher und übersichtlicher programmiert als die jeweils nicht-rekursive Variante.

Eine ähnliche Rolle spielen die sogenannten Nichtdeterminierten Endlichen Automaten in der Informatik. Wir wollen einen DEA konstruieren, der folgende Sprache hat:

L(A) = alle Worte über dem Alphabet S = {a, b},für die gilt: der vorletzte Buchstabe ist ein "a".

Die obige Abbildung zeigt die graphische Darstellung der Übergangsfunktion dieses Automaten. Sie macht einen reichlich komplizierten Eindruck. Das grundlegende Problem ist, dass der Automat nicht "weiß", wieviele Buchstaben auf den aktuellen Buchstaben noch folgen.

Betrachten Sie nun die graphische Darstellung der Übergangsfunktion eines äquivalenten Nichtdeterminierten Automaten ("äquivalent" heißt hier: Er hat die gleiche Sprache).

Die Übergangsfunktion macht einen reichlich komplizierten Eindruck. Das grundlegende Problem ist, dass der Automat nicht "weiß", wieviele Buchstaben auf den aktuellen Buchstaben noch folgen.

Betrachten Sie nun in der Abbildung links die graphische Darstellung der Übergangsfunktion eines äquivalenten Nichtdeterminierten Automaten ("äquivalent" heißt hier: Er hat die gleiche Sprache). Dieser Automat hat nur drei Zustände und nur drei Übergänge. Intuitiv "sieht" man, dass der Automat das Gewünschte leistet, denn am vorletzten Übergang (von 1 nach 2) steht nur der Buchstabe "a", und dann kann noch einmal ein "a" oder ein "b" folgen. Somit ist gewährleistet, dass der vorletzte Buchstabe immer ein "a" ist.

Und dennoch, irgendwie ist der Automat recht komisch, ja eigentlich unlogisch bis unmöglich. Betrachten wir dazu den Zustand 1. Mit dem Buchstaben "a" gelangen wir in den Zustand 2, aber gleichzeitig gelangen wir mit "a" auch wieder zurück in den Zustand 1. Es steht also keinesfalls fest, ob man mit dem Zeichen "a" in den Zustand 1 oder in den Zustand 2 gelangt. Deswegen bezeichnet man diesen Typ von Automaten als "nichtdeterminiert". Das Prädikat "endlich" gilt aber weiterhin, denn die Anzahl der Zustände dieses Automaten ist endlich.

2. Formales

Nichtdeterminierter Endlicher Automat (NDEA)

Ein nichtdeterminierter endlicher Automat (NDEA) ist ein 5-Tupel A = (Q,S, R ,q0,F) mit

Q = endliche Menge von Zuständen

S = Eingabealphabet

R = Übergangsrelation

q0 = Startzustand

F = endliche Menge von Endzuständen.

Bei einem NDEA kann also ein Zustand qn zwei verschiedene (oder mehrere) Ausgänge mit dem gleichen Eingabezeichen haben. Bei unserem Beispiel 1 gelangt man aus Zustand 1 mit dem Zeichen "a" in den Zustand 2 oder zurück in den Zustand 1. Wohin genau, ist nicht determiniert.

Der Vorteil dieser NDEAs: Man kann komplizierte DEAs auf sehr viel einfachere Weise darstellen, ähnlich wie eine rekursive Programmierung sehr viel einfachere Algorithmen erlaubt.

3. Umwandlung von NDEAs in DEAs

Ein kleines praktisches Problem gibt es noch: Man kann einen NDEA nicht in einen Algorithmus umsetzen. Ein Algorithmus ist nämlich grundsätzlich determiniert. Vielleicht ändert sich das ja eines Tages, wenn man mit den Quantencomputern weiter fortgeschritten ist, zur Zeit aber muss man genau festlegen, was das Programm machen soll, wenn bestimmte Bedingungen vorliegen.

Daher ist es erforderlich, einen NDEA in einen äquivalenten DEA umzuformen, wenn er irgendwie programmiert werden soll. Dieses Umformen geschieht mit Hilfe der sogenannten Teilmengenbeziehungen.

Betrachten wir dazu noch einmal die letzte Abbildung:

Wir beginnen mit dem Zustand 1 des NDEA. Dieser Startzustand ist gleichzeitig die erste Teilmenge des zu entwickelnden Diagramms (nächste Abbildung).

Erste Teilmenge: {1}

Wir wollen nun die zweite Teilmenge konstruieren. Mit dem Zeichen "a" kommt man einerseits in den Folgezustand 1 und andererseits in den Folgezustand 2.

Zweite Teilmenge: {1,2}

Wir können die beiden Teilmengen nun mit einem Pfeil verknüpfen und das Zeichen "a" an diesen Pfeil schreiben. Unser Teilmengendiagramm sieht dann so aus:

Nun überlegen wir, was passiert, wenn im Zustand 1 ein "b" kommt. Hier gibt es nur eine Möglichkeit, nämlich erneut Zustand 1. Die dritte Teilmenge besteht also nur aus dem Zustand 1 und ist damit identisch mit der ersten Teilmenge. Also können wir einen Pfeil auf die Menge { 1 } zurücklaufen lassen und ein "b" daran schreiben:

Da das Eingabealphabet S des Automaten nur aus den beiden Zeichen "a" und "b" besteht, haben wir für die erste Teilmenge {1} sämtliche Möglichkeiten abgehandelt.

Untersuchen wir nun die zweite Teilmenge {1, 2}. Was geschieht, wenn ein "a" kommt? Da die Teilmenge zwei Zustände umfasst, müssen wir diese Frage für jeden der beiden Zustände aus {1, 2} stellen.

Zustand 1 - Zeichen "a": Folgezustand 1 oder 2

Zustand 2 - Zeichen "a": Folgezustand 3

Die sich hieraus ergebende dritte Teilmenge umfasst also alle drei Zustände.

Dritte Teilmenge: {1, 2, 3}

Jetzt müssen wir die beiden Zustände der zweiten Teilmenge daraufhin untersuchen, welche Folgezustände das Zeichen "b" ergibt.

Zustand 1 - Zeichen "b": Folgezustand 1

Zustand 3 - Zeichen "b": Folgezustand 3

Die vierte Teilmenge besteht also aus den Zuständen 1 und 3.

Vierte Teilmenge: {1, 3}

Wir können unser Teilmengendiagramm also jetzt um zwei Teilmengen erweitern:

Nun nehmen wir uns die dritte Teilmenge {1, 2, 3} vor und schauen, was passiert, wenn der Buchstabe "a" erkannt wird. Wieder müssen wir diese Frage für alle drei Zustände der Teilmenge stellen:

Zustand 1 - Zeichen "a": Folgezustand 1 oder 2

Zustand 2 - Zeichen "a": Folgezustand 3

Zustand 3 - Zeichen "a": ---

Die sich hieraus ergebende Teilmenge umfasst wieder alle Zustände, ist also mit der dritten Teilmenge identisch. Wir ergänzen das Diagramm also um einen Pfeil, der von der dritten Teilmenge auf die dritte Teilmenge verweist:

Jetzt müssen wir für die dritte Teilmenge untersuchen, was bei einem "b" passiert:

Zustand 1 - Zeichen "b": Folgezustand 1

Zustand 2 - Zeichen "b": Folgezustand 3

Zustand 3 - Zeichen "b": ---

Die sich so ergebende Teilmenge ist identisch mit der vierten Teilmenge {1, 3}. Auch dies zeichnen wir als neuen Pfeil in das Diagramm ein:

Das Diagramm wird immer besser. Wir haben jetzt nur noch die Teilmenge {1, 3} zu untersuchen:

Zustand 1 - Zeichen "a": Folgezustand 1 oder 2

Zustand 3 - Zeichen "a": ---

Damit "landen" wir wieder in der Teilmenge {1, 2}. Wir müssen also einen Pfeil von der vierten Teilmenge zur zweiten zeichnen.

Zustand 1 - Zeichen "b": Folgezustand 1

Zustand 3 - Zeichen "b": ---

Jetzt kommen wir zur Teilmenge {1}, was mit der ersten Teilmenge identisch ist. Also zeichnen wir einen Pfeil zur Teilmenge 1 und erhalten dann das endgültige Teilmengendiagramm:

Wenn wir diese vier Teilmengen jetzt als Zustände eines DEAs interpretieren, kommen wir ganz schnell zu der Übergangsfunktion des äquivalenten DEAs:

Diese Abbildung kennen Sie bereits.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 26. Juli 2006.






IMPRESSUM