Theoretische Informatik

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

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.

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

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)

• mit dem regulären Ausdruck ST beschriftet, wenn keine Kante (s, s) vorhanden ist (Bild 3),
• mit dem regulären Ausdruck SX*T beschriftet, wenn eine Schlinge (s, s) vorhanden ist, die mit dem regulären Ausdruck X beschriftet ist (Bild 4).

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

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.

Aufgaben