Theoretische Informatik

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 {a} ⊆ A¹ und für die leere Menge ∅ sind in Bild 1 dargestellt:

R = a  mit  {a} ⊆ A1		NR  =
R = ∅		NR  =

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.¹)

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

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

R = S | T		NR  =
R = ST		NR  =
R = S*		NR  =

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.

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

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 nicht­deterministischen 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)