Theoretische Informatik

Konstruktion eines regulären Ausdrucks

aus einem nichtdeterministischen endlichen Automaten

 aufwärts

Gegeben ist ein nicht­deterministischer endlicher Automat N. Gesucht ist ein regulärer Ausdruck R, der genau die Sprache erzeugt, die der Automat N erkennt, d.h. L(R) = L(N).

Satz:  Zu jedem nicht­deterministischen endlichen Automaten N gibt es einen regulären Ausdruck R, der die von N erkannte Sprache L(N) erzeugt.

Zum Beweis des Satzes wird ein Verfahren angegeben, das einen beliebigen nicht­deterministischen endlichen Automaten in einen regulären Ausdruck umformt. Als Beispiel zur Ver­anschaulichung dient der in Bild 1 gezeigte nicht­deterministische endliche Automat N.

Bild 1: Umzuformender nichtdeterministischer endlicher Automat N
Bild 1: Umzuformender nichtdeterministischer endlicher Automat N

Das Verfahren ist die Umkehrung des Verfahrens zur Konstruktion eines nicht­deterministischen endlichen Automaten aus einem regulären Ausdruck.

Verfahren

In dem Verfahren werden aus dem Zustands­graphen des Automaten nach und nach die inneren Zustände entfernt und dafür die Kanten mit zunehmend komplexeren regulären Ausdrücken beschriftet. Zum Schluss besteht der Zustands­graph nur noch aus Startzustand und Endzustand und einem Zustands­übergang, der mit dem gesuchten regulären Ausdruck beschriftet ist.

Zunächst wird ein neuer Startzustand eingeführt und durch einen Epsilon-Übergang mit dem ursprüng­lichen Startzustand verbunden. Ferner wird ein neuer Endzustand eingeführt. Alle bisherigen Endzustände verlieren ihre Endzustands­eigenschaft; sie werden mit dem neuen Endzustand durch Epsilon-Übergänge verbunden (Bild 2).

Bild 2: Zustandsgraph des Automaten N mit neuem Start- und neuem Endzustand
Bild 2: Zustandsgraph des Automaten N mit neuem Start- und neuem Endzustand

Außer dem Startzustand und dem Endzustand werden nun schrittweise alle Zustände nach folgenden Regeln entfernt.

Wenn ein Zustand s entfernt wird, so wird jeder Kantenzug (r, s)(s, t) mit r, t ≠ s durch eine Kante (r, t) ersetzt. Sind hierbei die Kanten (r, s) und (s, t) mit den regulären Ausdrücken S bzw. T beschriftet, so wird die neue Kante (r, t)

Bild 3: Entfernen eines Zustandes
Bild 3: Entfernen eines Zustandes
Bild 4: Entfernen eines Zustandes mit Schlinge
Bild 4: Entfernen eines Zustandes mit Schlinge

Ist nach dem Entfernen eines Zustands eine Doppelkante zwischen zwei Zuständen vorhanden, so wird diese durch eine einfache Kante ersetzt. Die Beschriftung dieser neuen Kante ist S | T, wenn S bzw. T die Beschriftungen der Doppelkante waren (Bild 5).

Bild 5: Ersetzen einer Doppelkante
Bild 5: Ersetzen einer Doppelkante

Beispiel

Folgendes Bild 6 zeigt die Anwendung des Verfahrens auf den als Beispiel angegebenen Automaten. Das Ergebnis ist ein Zustands­graph, dessen einziger Zustands­übergang mit dem gesuchten regulären Ausdruck beschriftet ist.

Bild 6: Schrittweises Entfernen von Zuständen
Bild 6: Schrittweises Entfernen von Zuständen

Aufgaben

Aufgabe 1:  Gegeben ist folgender (deterministische) endliche Automat, der alle Wörter über dem Alphabet A = {a, b} erkennt, die eine gerade Anzahl von b's enthalten.

Automat

Erzeugen Sie nach dem angegebenen Verfahren aus dem Automaten einen regulären Ausdruck.

 

Aufgabe 2:  Gegeben ist folgender (deterministische) endliche Automat, der alle Wörter über dem Alphabet A = {a, b} erkennt, die eine gerade Anzahl von a's und von b's enthalten.

Automat

Erzeugen Sie nach dem angegebenen Verfahren aus dem Automaten einen regulären Ausdruck.

 

Weiter mit:  [Konstruktion eines deterministischen aus einem nichtdet. endl. Automaten]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 19.04.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