Theoretische Informatik

Konstruktion eines nicht­deterministischen endlichen Automaten

aus einem regulären Ausdruck (top-down)

 aufwärts

Gegeben ist ein regulärer Ausdruck R und ein Wort w. Es stellt sich die Frage, ob w von R erzeugt wird, d.h. ob w in der von R erzeugten regulären Sprache L(R) enthalten ist.

Diese Frage ist auf direktem Wege im allgemeinen schwer zu beantworten. Meist ist es nicht offensichtlich, ob es eine Möglichkeit gibt, das Wort w aus dem regulären Ausdruck R zu erzeugen. Eine systematische Methode zur Entscheidung der Frage geht den Umweg über einen nicht­deterministischen endlichen Automaten.

Hierzu wird aus dem regulären Ausdruck R ein nicht­deterministischer endlicher Automat N konstruiert. Der Automat wird so konstruiert, dass er genau alle jene Wörter akzeptiert, die zu L(R) gehören.

Satz:  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.

Zum Beweis des Satzes wird im Folgenden ein Verfahren angegeben, mit dem der Zustands­graph des entsprechenden Automaten rekursiv aus dem gegebenen regulären Ausdruck konstruiert wird. Hierbei wird der reguläre Ausdruck top-down in immer kleinere reguläre Ausdrücke zerlegt und parallel dazu der Zustands­graph des Automaten konstruiert.

Ein anderes Verfahren baut den regulären Ausdruck bottom-up aus Teilausdrücken auf und konstruiert parallel dazu den Zustands­graphen des Automaten. Das entsprechende Verfahren ist in Konstruktion eines nicht­deterministischen endlichen Automaten (bottom-up) beschrieben.

 

Verfahren

Als erstes wird ein Zustands­graph mit einem Startzustand und einem Endzustand erzeugt. Startzustand und Endzustand sind durch einen Zustands­übergang miteinander verbunden, der mit dem regulären Ausdruck R beschriftet ist (Bild 1). Dieser Zustands­graph beschreibt offenbar das Verhalten eines Automaten, der die regulären Sprache L(R) erkennt – allerdings nur ganz grob, die inneren Zustände des Automaten bleiben zunächst unbestimmt.

Anfangssituation
Bild 1:  Anfangssituation

Durch Zerlegung dieses Zustands­übergangs werden nach und nach die inneren Zustände des Automaten erzeugt. Dabei gelten folgende Regeln:

  1. Jeder Zustands­übergang, der mit S | T beschriftet ist, wird in zwei parallele Zustands­übergänge zerlegt, die mit S bzw. mit T beschriftet sind (Bild 2a).
  2. Jeder Zustands­übergang, der mit ST beschriftet ist, wird in zwei aufeinander folgende Zustands­übergänge zerlegt, die mit S bzw. mit T beschriftet sind (Bild 2b).
  3. Jeder Zustands­übergang, der mit S* beschriftet ist, wird wie in Bild 2c gezeigt zerlegt.
Zerlegen der Zustandsübergänge S|T, ST und S*
Bild 2:  Zerlegen der Zustands­übergänge S|T, ST und S*

Am Ende des Verfahrens werden parallele Zustands­übergänge, die mit einzelnen Zeichen beschriftet sind, zu einem Zustands­übergang zusammen­gefasst, so dass jeder Zustands­übergang mit einer Elementar­sprache beschriftet ist. Das Ergebnis ist der Zustands­graph des gesuchten nicht­deterministischen endlichen Automaten.

Der erzeugte Automat enthält im allgemeinen Epsilon-Übergänge. Durch anschließende Beseitigung dieser Epsilon-Übergänge mithilfe des bekannten Verfahrens lässt sich auch ein nicht­deterministischer endlicher Automat ohne Epsilon-Übergänge erzeugen.

 

Beispiel

Als Beispiel zur Ver­anschaulichung dient der reguläre Ausdruck

R  =  a(a | b)*a | a

In Bild 3 sind die einzelnen Schritte des Verfahrens dargestellt.

Konstruktion am Beispiel des regulären Ausdrucks a(a | b)*a | a
Bild 3:  Konstruktion am Beispiel des regulären Ausdrucks a(a | b)*a | a

 

Aufgabe

Aufgabe 1:  Konstruieren Sie nach dem angegebenen Verfahren einen nicht­deterministischen endlichen Automaten N aus dem regulären Ausdruck

R   =   (a | ba | bba)*(ε | b | bb)

über dem Alphabet A = {a, b}. Die erzeugte bzw. erkannte Sprache umfasst alle Wörter über A, die höchstens zwei b's hintereinander enthalten.

 

 

Weiter: [Konstruktion eines regulären Ausdrucks aus einem endlichen Automaten]   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 29.10.2013
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik