Theoretische Informatik

Konstruktion eines nichtdeterministischen endlichen Automaten

aus einem regulären Ausdruck (bottom-up)

 aufwärts

Zu jedem regulären Ausdruck R gibt es einen nicht­deterministischen endlichen Automaten N, der die von R erzeugte reguläre Sprache L(R) erkennt.

Der nicht­deterministische endliche Automat N lässt sich entweder top-down oder bottom-up induktiv über den Aufbau von R konstruieren. Das Top-Down-Verfahren beginnt mit einem erweiterten Automaten mit zwei Zuständen, dessen einziger Zustands­übergang mit R markiert ist, und zerlegt diesen nach und nach. Das Bottom-Up-Verfahren beginnt mit elementaren Automaten für die Elementar­sprachen, die in R enthalten sind, und setzt diese nach und nach zusammen [AHU 74]. Dieses Verfahren ist im Folgenden dargestellt. Das andere Verfahren ist in Konstruktion eines nicht­deterministischen endlichen Automaten (top-down) beschrieben.

Verfahren

Die elementaren Automaten für die Elementar­sprachen {aenthalten in A1 und für die leere Menge  leere Menge  sind in Bild 1 dargestellt:

 

R = a  mit  {aenthalten in A1 NR  =  Automat für a
  
  
R =  leere Menge  NR  =  Automat für die leere Menge
Bild 1: Elementare Automaten für die regulären Ausdrücke R = a und R =  leere Menge 

Wenn also der reguläre Ausdruck R nur aus der Elementar­sprache {a} besteht, dann ist der zugehörigen Automat N sehr einfach: Er hat einen Startzustand, einen Endzustand und einen Zustands­übergang, nämlich vom Startzustand zum Endzustand unter dem Zeichen a. Der Automat erkennt dann genau die Sprache {a}.

Wenn der reguläre Ausdruck R die leere Menge ist, besteht der zugehörige Automat aus Start- und Endzustand, die jedoch durch keinen Zustands­übergang verbunden sind. Daher ist der Endzustand nicht erreichbar. Der Automat kann also nie in den Endzustand gelangen; die erkannte Sprache ist daher die leere Menge.1)

 

Seien nun S und T reguläre Ausdrücke und NS und NT die zugehörigen Automaten, wie in Bild 2 schematisch dargestellt.

Bild 2: Schematische Darstellung der Automaten NS und NT
Bild 2: Schematische Darstellung der Automaten NS und NT

Dann werden die Automaten für S | T, ST und S* wie in Bild 3 dargestellt konstruiert:

 

R = S | T NR  =   Automat für S | T
   
   
R = ST NR  =   Automat für ST
   
   
R = S* NR  =   Automat für S*
Bild 3: Automaten für  S | TST  und  S*

Die auf diese Weise konstruierten Automaten enthalten viele Epsilon-Übergänge. Die Anzahl der Zustände ist dadurch größer als eigentlich notwendig. Auf der anderen Seite haben die Automaten jedoch einige Eigen­schaften, die für die Implementation vorteilhaft sind:

  1. Jeder Zustand hat höchstens zwei Folge­zustände.
  2. Hat ein Zustand zwei Folge­zustände, so führen ε-Übergänge dorthin.
  3. Ein Zustand ist genau dann Endzustand, wenn er keinen Folgezustand hat.
  4. Es gibt genau einen Endzustand.

 

Beispiel:  Folgendes Bild 4 zeigt den nach dieser Methode konstruierten nicht­deterministischen endlichen Automaten N, der zu dem regulären Ausdruck R = (a | b)*a gehört.

Bild 4: Nichtdeterministischer endlicher Automat für (a | b)*a
Bild 4: Nichtdeterministischer endlicher Automat für (a | b)*a

Recursive-Descent-Übersetzung von regulären Ausdrücken

Um für einen beliebigen regulären Ausdruck R und ein beliebiges Wort w über einem Alphabet A zu entscheiden, ob w von R erzeugt wird, sind zwei Schritte nötig:

  1. Konstruktion eines nicht­deterministischen endlichen Automaten N zu dem regulären Ausdruck R
  2. Simulation des nicht­deterministischen endlichen Automaten N mit dem Eingabewort w

Wenn der Automat das Wort erkennt, wird es von dem regulären Ausdruck erzeugt und sonst nicht.

Es wird jetzt noch ein Verfahren gebraucht, das den Aufbau eines regulären Ausdrucks analysiert und nach der oben beschriebenen Methode den zugehörigen nicht­deterministischen endlichen Automaten konstruiert. In klassischer Weise wird dies von einem Recursive-Descent-Übersetzer geleistet, der einen regulären Ausdruck in den zugehörigen nicht­deterministischen endlichen Automaten übersetzt. Das folgende Bild 5 illustriert diese Vorgehens­weise:

Bild 5: Prüfen, ob das Wort w von dem regulären Ausdruck R erzeugt wird
Bild 5: Prüfen, ob das Wort w von dem regulären Ausdruck R erzeugt wird

Visualisierung

In folgendem Applet wird durch Recursive-Descent-Übersetzung aus einem regulären Ausdruck ein nicht­deterministischer endlicher Automat konstruiert, der die zugehörige reguläre Sprache erkennt.

Bei Eingabe eines syntaktisch nicht korrekten regulären Ausdrucks wird eine Fehler­meldung sowie die Position des Fehlers ausgegeben.

Der Automat wird als Zustands­graph ausgegeben; hierbei stehen Pfeile ohne Markierung für Epsilon-Übergänge.

Das Alphabet besteht hier nur aus den Symbolen a, b, c. Das Zeichen % steht für die leere Menge.

 

(Java-Applet zur Konstruktion eines nichtdeterministischen endlichen Automaten aus einem regulären Ausdruck)

Literatur

[AHU 74]A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Die Konstruktion eines nichtdeterministischen endlichen Automaten kommt in der hier vorgestellten Form auch in meinem Buch über Algorithmen vor.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

1)  Der Epsilon-Übergang ist nötig, damit der Automat die unten angegebenen Bedingungen 3 und 4 erfüllt.

 

Weiter mit:   [Recursive-Descent-Übersetzung], [Übersetzung regulärer Ausdrücke]   oder   up

 

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

Hochschule Flensburg
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