Umwandlung von endlichen Automaten in reguläre Ausdrücke

Umwandlung von endlichen Automaten in reguläre Ausdrücke
Wir werden sehen, wie man aus einem endlichen Automaten M einen regulären Ausdruck γ
konstruieren kann, der genau die von M akzeptierte Sprache erzeugt. Die Konstruktion enfernt
schrittweise Zustände aus dem Automaten und ersetzt die Beschriftungen der Kanten durch
reguläre Ausdrücke. Am Ende besteht der Automat nur noch aus einem Start- und einem Endzustand, zwischen denen eine Kante liegt, die mit dem gesuchten regulären Ausdruck beschriftet
ist.
Zuerst schauen wir uns an einem Beispiel an, wie ein Zustand entfernt werden kann und sich
dadurch die Beschriftung der Kanten im endlichen Automaten ändert. In diesem Beispiel wollen
wir die Menge aller Wörter, mit denen man von Zustand 1 zu Zustand 4 kommt, durch einen
regulären Ausdruck beschreiben.
b
a
b
b
1
a
2
a
3
4
a
Zustand 2 soll zuerst entfernt werden. Aus Zustand 1 gelangt man über Zustand 2 zu Zustand
3 — zum Beispiel durch die Eingabe aa oder abbba. Allgemein lassen sich alle Wörter, durch
die man von Zustand 1 über Zustand 2 zu Zustand 3 gelangt, mit ab∗ a beschreiben. Mit diesem
regulären Ausdruck beschriftet man die neue Kante von Zustand 1 zu Zustand 3 nach Entfernen
von Zustand 2. Weitere Kanten sind nicht betroffen.
a
b
b
1
ab∗ a
3
4
a
Nun soll Zustand 3 entfernt werden. Davon sind zwei Wege betroffen. Von Zustand 1 kommt man
über Zustand 3 zu Zustand 4, und von Zustand 4 kommt man über Zustand 3 wieder zu Zustand
4. Betrachten wir zuerst den ersten betroffenen Weg. Bisher gibt es keine Kante von Zustand 1
zu Zustand 4. Damit diese Verbindung auch nach dem Entfernen von Zustand 3 erhalten bleibt,
muss eine neue Kante von Zustand 1 zu Zustand 4 eingefügt werden. Ihre Beschriftung setzt
sich zusammen aus
1. der Beschriftung ab∗ a der Kante von Zustand 1 zu Zustand 3 — gefolgt von
2. der Beschriftung a der Kante von Zustand 3 zu Zustand 3; da diese Kante beliebig oft
wiederholt durchlaufen werden kann, wird diese Beschriftung mit einem ∗ versehen (das
haben wir oben auch so gemacht) — gefolgt von
3. der Beschriftung b der Kante von Zustand 3 zu Zustand 4
Insgesamt ergibt das die Beschriftung ab∗ a a∗ b.
Nun zum zweiten betroffenen Weg. Von Zustand 4 kann man einen Schritt zu Zustand 3 machen
und von dort wieder in einem Schritt zu Zustand 4 gehen. Deshalb muss die Schleife über Zustand
4 ebenfalls neu beschriftet werden. Um von Zustand 4 zu Zustand 4 zu kommen, hat man zwei
Möglichkeiten. Entweder man benutzt die Schleife über Zustand 4 – sie ist mit b beschriftet –
oder man macht den Abstecher über Zustand 3 – nach dem obigen Schema ergibt der Abstecher
die Beschriftung aa∗ b. Da man zwischen diesen beiden Alternativen wählen kann, ensteht die
1
Beschriftung der Kante aus erste Alternative | zweite Alternative, hier also b | aa∗ b. Damit ergibt
sich nach dem Entfernen von Zustand 3 folgender Automat.
b | aa∗ b
1
ab∗ a a∗ b
4
An den Kantenbeschriftungen kann man ablesen, mit welchen Wörtern man von Zustand 1 zu
Zustand 4 kommt. Mit allen Wörtern, die durch ab∗ a a∗ b beschrieben werden, kommt man
von Zustand 1 (erstmals) zu Zustand 4, und mit allen Wörtern, die durch b | aa∗ b beschrieben
werden, bleibt man in Zustand 4. Insgesamt beschreibt dann der reguläre Ausdruck
ab∗ a a∗ b ( ε | (b | aa∗ b)∗ )
die Menge aller Wörter, mit denen man von Zustand 1 zu Zustand 4 kommt. Das ε steht
abkürzend für den regulären Ausdruck ∅∗ , der die Menge {ε} beschreibt.
Das soll nun alles formaler – und damit klar nachvollziehbar und allgemein anwendbar – dargestellt werden. Wir bezeichnen die Beschriftung der Kante von Zustand s zu Zustand t mit
R(s, t). Im letzten Beispiel ist R(1, 4) = ab∗ aa∗ b und R(4, 4) = b | aa∗ b. Wenn es keine Kante
von s zu t gibt, dann fassen wir das als Beschriftung R(s, t) = ∅ auf. Im letzten Beispiel ist
R(4, 1) = ∅ und R(1, 1) = ∅.
Beim Entfernen von Zustand x muss man für jedes Paar s, t von Zuständen eine neue Beschriftung Rneu (s, t) bestimmen. Die neue Beschriftung besteht aus der Alternative der alten
Beschriftung R(s, t) und der Beschriftung eines Weges von s nach t mit einem Abstecher über
x. Wie oben beschrieben ist diese Beschriftung R(s, x) R(x, x)∗ R(x, t) – also zuerst ein Schritt
von s zu x, dann eine Schleife in x, und zuletzt der Schritt von x zu t. Formal beschreibt man
das wie folgt:
Rneu (s, t) = R(s, t) | R(s, x) R(x, x)∗ R(x, t)
Aus einem Automaten mit den Zuständen {z1 , z2 , . . . , zn } und den durch R gegebenen Kantenbeschriftungen erhält man nach Entfernen von Zustand zi einen Automaten mit den Zuständen
{z1 , z2 , . . . , zn } − {zi } und den durch Rneu bestimmten Kantenbeschriftungen.
Die Umwandlung eines endlichen Automaten in einen regulären Ausdruck geschieht nun durch
schrittweises Entfernen der Zustände und Bestimmung der neuen Kantenbeschriftungen. Am
Ende soll genau ein Startzustand und ein Endzustand übrig bleiben, so dass die Beschriftung
der Kante zwischen diesen beiden Zuständen der gesuchte reguläre Ausdruck ist. Das geht nur,
wenn der Startzustand am Anfang keine eingehende Kante und der Endzustand keine ausgehende
Kante besitzt. Dazu muss man den Automaten nochmal umbauen. Zuerst fügt man einen neuen
Zustand hinzu, der eine ε-Kante zum alten Startzustand hat. Dieser neue Zustand ist dann der
Startzustand des umgebauten Automaten. Dann fügt man einen weiteren neuen Zustand hinzu,
zu dem es eine ε-Kante von jedem Endzustand gibt. Dieser neue Zustand ist dann der einzige
Endzustand des umgebauten Automaten. Nun kann man schrittweise alle Zustände bis auf den
Start- und den Endzustand entfernen. Die Reihenfolge, in der man die Zustände entfernt, ist
egal. Am Ende bleibt ein Automat übrig, der aus zwei Zuständen besteht: dem Startzustand
und dem Endzustand. Es führt eine Kante vom Start- zum Endzustand, die mit dem regulären
Ausdruck beschriftet ist, der den ursprünglichen endlichen Automaten beschreibt, mit dem man
mal begonnen hat.
2
Erstes Beispiel
Als Beispiel schauen wir uns einen Automaten an, der alle Binärwörter akzeptiert, die keine
durch 3 teilbaren Binärzahlen darstellen. (Wir erlauben hier auch führende 0en.) Der Zustand
gibt an, welchen Rest mod 3 das Binärwort hat, mit dem der Zustand erreicht wurde.
0
start
1
1
0
1
00
1
2
Schritt 1: Füge einen neue Startzustand und einen neuen Endzustand hinzu.
0
ε
Start
1
1
0
1
0
1
ε
0
ε
2
Ende
Nun werden schrittweise alle Zustände bis auf den Start- und den Endzustand entfernen.
Schritt 2: Entferne Zustand 2.
Alle Kantenbeschriftungen müssen erneuert werden mittels der Regel
Rneu (s, t) = R(s, t) | R(s, 2) R(2, 2)∗ R(2, t) .
Wenn R(s, 2) = ∅ oder R(2, t) = ∅, dann ist R(s, 2) R(2, 2)∗ R(2, t) = ∅ und folglich Rneu (s, t) =
R(s, t). In diesem Fall ändert sich die Beschriftung also nicht.
Damit sieht man, dass hier nur die Kante von Zustand 1 zu Zustand Ende und die Kante von
Zustand 1 zu Zustand 1 neu beschriftet werden müssen.
1. Rneu (1, Ende) = R(1, Ende) | R(1, 2) R(2, 2)∗ R(2, Ende)
= ε | 01∗ ε
= ε | 01∗
2. Rneu (1, 1) = R(1, 1) | R(1, 2) R(2, 2)∗ R(2, 1)
= ∅ | 01∗ 0
= 01∗ 0
Die Beschriftung aller anderen Kanten bleibt unverändert.
01∗ 0
0
Start
ε
0
1
1
3
ε | 01∗
1
Ende
Schritt 3: Entferne Zustand 0.
Von Zustand Start zu Zustand 1 muss eine neue Kante eingefügt werden, damit man von Start
zu 1 mit einem Abstecher über Zustand 0 gehen kann.
Rneu (Start, 1) = R(Start, 1) | R(Start, 0) R(0, 0)∗ R(0, 1)
=
∅ | ε0∗ 1
=
0∗ 1
Die Schleife über Zustand 1 muss neu beschriftet werden.
Rneu (1, 1) = R(1, 1) | R(1, 0) R(0, 0)∗ R(0, 1)
= 01∗ 0 | 10∗ 0
Die Kante von Zustand 1 zu Zustand Ende muss nicht neu beschriftet werden, da kein Abstecher
über Zustand 0 die beiden Zustände verbindet.
01∗ 0 | 10∗ 1
Start
0∗ 1
ε | 01∗
1
Ende
Schritt 4: Entferne Zustand 1.
Die einzige verbleibende Kante muss neu beschriftet werden.
0∗ 1 (01∗ 0 | 10∗ 1)∗ (ε | 01∗ )
Start
Ende
Damit ergibt sich, dass
Rneu (Start, Ende) = 0∗ 1 (01∗ 0 | 10∗ 1)∗ (ε | 01∗ )
der reguläre Ausdruck ist, der die vom ursprünglichen Automaten akzeptierte Sprache beschreibt
– also die Menge aller Binärzahlen, die nicht durch 3 teilbar sind.
Zweites Beispiel
Hier schauen wir uns einen recht kleinen endlichen Automaten an, für den der reguläre Ausdruck
recht groß wird. Der endliche Automat akzeptiert die Sprache
A = {w ∈ {a, b}∗ | die Anzahl der a in w ist gerade und die Anzahl der b in w ist ungerade} .
Die Bezeichnung der Zustände ist so gewählt, dass das erste Zeichen (G oder U) angibt, ob
die Anzahl der bisher gelesenen a gerade (G) oder ungerade (U) ist. Das zweite Zeichen der
Zustandsbezeichnung gibt das entsprechende für b an. Der Zustand UG wird also erreicht, wenn
eine Ungerade Anzahl a und eine Gerade Anzahl b gelesen wurde.
4
a
start
GG
b
UG
a
b
b
b
a
GU
UU
a
Schritt 1: Füge einen neuen Startzustand und einen neuen Endzustand hinzu.
a
ε
Start
GG
b
UG
a
b
b
b
a
Ende
GU
ε
UU
a
Schritt 2: Zustand UG wird entfernt.
Folgende Beschriftungen sind betroffen.
1. Rneu (GG, GG) = R(GG, GG) | R(GG, UG)R(UG, UG)∗ R(UG, GG) = ∅ | a ∅∗ a = aa
2. Rneu (GG, UU) = R(GG, UU) | R(GG, UG)R(UG, UG)∗ R(UG, UU) = ∅ | a ∅∗ b = ab
3. Rneu (UU, UU) = R(UU, UU) | R(UU, UG)R(UG, UG)∗ R(UG, UU) = ∅ | b ∅∗ b = bb
4. Rneu (UU, GG) = R(UU, GG) | R(UU, UG)R(UG, UG)∗ R(UG, GG) = ∅ | b ∅∗ a = ba
aa
Start
ε
GG
ba
b
b
ab
a
Ende
ε
GU
a
UU
Schritt 3: Zustand UU wird entfernt.
Alle Kanten (mit Ausnahme der ε-Kanten) werden neu beschriftet.
5
bb
aa | ab(bb)∗ ba
ε
Start
GG
b|ab(bb)∗ a
Ende
b|a(bb)∗ ba
GU
ε
a(bb)∗ a
Schritt 4: Zustand GG wird entfernt.
Eine Kante vom Startzustand zu GU wird hinzugenommen. Bei der Beschriftung ist zu beachten,
dass
Rneu (Start, GU) = R(Start, GU) | R(Start, GG)R(GG, GG)∗ R(GG, GU)
= R(GG, GG)∗ R(GG, GU)
da R(Start, GU) = ∅ und R(Start, GG) = ε.
Start
(aa|ab(bb)∗ ba)∗ (b|ab(bb)∗ a)
|
{z
}|
{z
}
R(GG,GG)∗
Ende
ε
GU
R(GG,GU)
a(bb)∗ a | (b|a(bb)∗ ba) (aa|ab(bb)∗ ba)∗ ) (b|ab(bb)a)
| {z }
|
{z
}|
{z
} | {z }
R(GU,GU)
R(GU,GG)
R(GG,GG)∗
R(GG,GU)
Schritt 5: Zustand GU wird entfernt.
Start
(aa|ab(bb)∗ ba)∗ (b|ab(bb)∗ a) (a(bb)∗ a | (b|a(bb)∗ ba)(aa|ab(bb)∗ ba)∗ )(b|ab(bb)∗ a))∗
|
{z
} |
{z
}
R(GU,GU)∗
R(Start,GU)
Ende
Damit ist der reguläre Ausdruck für den ursprünglichen Automaten bestimmt.
6

Download Report