Theoretische Informatik

Konstruktion eines deterministischen endlichen Automaten

aus einem nichtdeterministischen endlichen Automaten

 aufwärts

Gegeben ist ein nicht­deterministischer endlicher Automat N. Gesucht ist ein deterministischer endlicher Automat D, der dieselbe Sprache erkennt, d.h. für den gilt: L(D) = L(N).

Deterministischer endlicher Automat

Die Übergangs­relation eines nicht­deterministischen endlichen Automaten kann so beschaffen sein, dass manche Zustände mehrere Folge­zustände unter einem bestimmten Eingabe­zeichen a Element A haben, manche Zustände dagegen gar keinen Folgezustand unter einem bestimmten Eingabe­zeichen a Element A. Bei einem deterministischen endlichen Automaten ist dies nicht erlaubt. Beim deterministischen endlichen Automaten hat jeder Zustand unter jedem Eingabe­zeichen a Element A genau einen Folgezustand. Die Übergangs­relation eines deterministischen endlichen Automaten ist eindeutig und total definiert – und damit eine Übergangsfunktion:

d : Z × A Pfeil nach rechts Z

Ein deterministischer endlicher Automat ist somit nicht das Gegenteil, sondern ein Spezialfall eines nicht­deterministischen endlichen Automaten.

Beispiel:  Der in Bild 1 dargestellte Automat ist (echt) nicht­deterministisch, denn der Zustand 0 hat unter dem Eingabe­zeichen a zwei Folge­zustände, nämlich 0 und 1. Außerdem hat der Zustand 1 unter dem Eingabe­zeichen a keinen Folgezustand. Der Zustand 2 hat weder unter a noch unter b einen Folgezustand.

Bild 1: Nichtdeterministischer endlicher Automat N
Bild 1: Nichtdeterministischer endlicher Automat N

Die Übergangs­funktion eines deterministischen endlichen Automaten ist nur auf Z × A definiert, daher sind in einem deterministischen endlichen Automaten keine Epsilon-Übergänge erlaubt.

Teilmengenkonstruktion

Aus jedem nicht­deterministischen endlichen Automaten lässt sich ein deterministischer endlicher Automat konstruieren. Die Idee der Konstruktion besteht darin, während der Simulation des nicht­deterministischen endlichen Automaten sozusagen "Moment­aufnahmen" zu machen. Diese Moment­aufnahmen unter­scheiden sich dadurch, dass auf ihnen unter­schiedliche Zustände markiert sind. Die Menge dieser unter­schiedlichen Moment­aufnahmen bildet die Zustands­menge des deterministischen endlichen Automaten (Bild 2).

Oder genauer ausgedrückt, diejenigen Teilmengen der Zustands­menge des nicht­deterministischen endlichen Automaten, die während der Simulation jeweils markiert sein können, werden sozusagen als "Super­zustände" aufgefasst und zu den Zuständen des deterministischen endlichen Automaten erklärt.

Die Zustände des deterministischen endlichen Automaten sind also Teilmengen der Zustands­menge des nicht­deterministischen endlichen Automaten, daher wird das Verfahren als Teilmengen­konstruktion bezeichnet.

Bild 2: 'Momentaufnahmen' bei der Simulation eines nichtdeterministischen endlichen Automaten
Bild 2: "Momentaufnahmen" bei der Simulation eines nichtdeterministischen endlichen Automaten

Die folgende Simulation des oben angegebenen nicht­deterministischen endlichen Automaten zeigt, dass die Teilmengen {0}, {0, 1} und {0, 2} markiert sein können; der Automat befindet sich also sozusagen jeweils in einem dieser drei Super­zustände:

 

(Java-Applet zur Simulation eines nichtdeterministischen endlichen Automaten)

 

Verfahren

Mit dem folgenden Verfahren wird ein nicht­deterministischer endlicher Automat N in einen deterministischen endlichen Automaten D umgeformt. Als Beispiel zur Ver­anschaulichung dient der in Bild 1 gezeigte nicht­deterministische endliche Automat, der die reguläre Sprache L  =  (a|b)*ab erkennt.

Das hier beschriebene Verfahren geht von einem nicht­deterministischen endlichen Automaten ohne Epsilon-Übergänge aus; es lässt sich aber für nicht­deterministische endliche Automaten mit Epsilon-Übergängen anpassen (siehe Aufgabe 2).

Teilmengen­konstruktion
  1. Zustands­menge des zu konstruierenden deterministischen endlichen Automaten D ist zunächst die Potenzmenge Potenzmenge(Z) der Zustands­menge Z des nicht­deterministischen endlichen Automaten N, d.h. die Menge aller Teilmengen von Z. Es wird sich zeigen, dass diese Zustände im allgemeinen nicht alle gebraucht werden, etliche können möglicher­weise später wieder entfallen.
    1. Startzustand von D ist die Teilmenge {q}, wobei q der Startzustand von N ist.
    2. Endzustände sind alle Teilmengen T mit T Durchschnitt F ≠  leere Menge , wobei F die Menge der Endzustände von N ist. D.h. eine Teilmenge T ist Endzustand von D, wenn sie einen Endzustand von N enthält.

     

    Bild 3 zeigt die Menge der Zustände des deterministischen endlichen Automaten D. Die Teilmenge {0} ist der Startzustand, die Teilmengen {2}, {0, 2}, {1, 2} und {0, 1, 2} sind Endzustände, weil sie den Endzustand 2 von N enthalten.

    Bild 3: Zustände des zu konstruierenden deterministischen endlichen Automaten D
    Bild 3: Zustände des zu konstruierenden deterministischen endlichen Automaten D
  2. Die Übergangs­funktion des deterministischen endlichen Automaten D wird folgender­maßen aus der Übergangs­relation d des nicht­deterministischen endlichen Automaten N konstruiert:

    Folgezustand T ' eines Zustands T von D unter einem Eingabe­zeichen a Element A ist die Teilmenge

    T '  =  { s'  |   es existiert s Element T :  (s, a, s'Element d }.

    T ' besteht also aus den Folge­zuständen aller Zustände s Element T unter dem Eingabe­zeichen a in N.

    Als erstes werden die Folge­zustände des Start­zustands T = {q} berechnet, dann deren Folge­zustände usw., solange, bis keine weiteren Zustands­übergänge mehr hinzu kommen. Es zeigt sich, dass meist gar nicht alle Zustände vom Startzustand aus erreichbar sind; diese Zustände können entfallen, die Zustands­übergänge zwischen ihnen brauchen nicht berechnet zu werden.

     

    In Bild 4 ist zu sehen, dass in D die Teilmenge T ' = {0, 1} der Folgezustand von T = {0} unter dem Eingabe­zeichen a ist, weil in N die Zustände 0 und 1 Folge­zustände von 0 unter dem Eingabe­zeichen a sind.

    Der Folgezustand von T = {0, 1} unter dem Eingabe­zeichen b ist T ' = {0, 2}, denn in N ist 0 Folgezustand von 0 unter b und 2 ist Folgezustand von 1 unter b.

    Entsprechend ergeben sich die anderen in Bild 4 einge­zeichneten Zustands­übergänge. Die weiteren Zustands­übergänge für die Zustände  leere Menge , {1}, {2}, {1, 2} und {0, 1, 2} brauchen nicht berechnet zu werden, da diese Zustände vom Startzustand {0} aus nicht erreichbar sind.

    Bild 4: Konstruktion der Übergangsrelation des deterministischen endlichen Automaten D
    Bild 4: Konstruktion der Übergangsrelation des deterministischen endlichen Automaten D
  3. Überflüssige Zustände, also Zustände von D, die vom Startzustand {q} aus nicht erreichbar sind, werden entfernt.

    Bild 5 zeigt den deterministischen endlichen Automaten D ohne diese über­flüssigen Zustände.

    Bild 5: Deterministischer endlicher Automat D ohne überflüssige Zustände
    Bild 5: Deterministischer endlicher Automat D ohne überflüssige Zustände

 

Wenn es im Zustands­graphen von N einen Pfad vom Startzustand zu einem Endzustand gibt, der mit w beschriftet ist, so gibt es aufgrund der Konstruktion auch in D einen Pfad vom Startzustand zu einem Endzustand, der mit w beschriftet ist. Umgekehrt gilt dasselbe. Die beiden Automaten erkennen also dieselbe Sprache, d.h. es ist L(D) = L(N).

Ergebnis

Die eben gezeigte Konstruktion eines deterministischen endlichen Automaten aus einem nicht­deterministischen endlichen Automaten bildet die Grundlage für folgenden Satz.

Satz:  Zu jedem nicht­deterministischen endlichen Automaten N gibt es einen deterministischen endlichen Automaten D, der dieselbe Sprache erkennt, und umgekehrt.

Beweis:  

N  Pfeil nach rechts  D: D wird durch die Teilmengen­konstruktion aus N erzeugt
D  Pfeil nach rechts  N: N = D, da ein deterministischer endlicher Automat ein Spezialfall eines nicht­deterministischen endlichen Automaten ist.

Die regulären Sprachen werden also von den nicht­deterministischen und den deterministischen endlichen Automaten erkannt.

Aufgaben

Aufgabe 1:  Gegeben sei der folgende nicht­deterministische endliche Automat N (Bild 6). Erzeugen Sie aus N mit Hilfe der Teilmengen­konstruktion einen deterministischen endlichen Automaten D, der dieselbe Sprache erkennt.

Bild 6: Nichtdeterministischer endlicher Automat N
Bild 6: Nichtdeterministischer endlicher Automat N

Aufgabe 2:  Formulieren Sie ein Verfahren, das einen deterministischen endlichen Automaten aus einem nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen konstruiert.

Hinweis: Benutzen Sie den Begriff der Epsilon-Hülle bei der Angabe der Konstruktionsschritte.

 

Weiter mit:  [Komplexität deterministischer endl. Automaten]   [Pumping Lemma]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 08.06.2007   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik