Theoretische Informatik

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 offen­sichtlich, 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.

Zum Beweis des Satzes wird im Folgenden ein Verfahren angegeben, mit dem der Zustands­graph des ent­sprechenden 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 Teil­ausdrücken auf und konstruiert parallel dazu den Zustands­graphen des Automaten. Das ent­sprechende 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.

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.

Am Ende des Verfahrens werden parallele Zustands­übergänge, die mit einzelnen Zeichen beschriftet sind, zu einem Zustands­übergang zusammen­gefasst, sodass 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.

Aufgabe