close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

5. November

EinbettenHerunterladen
108
Minimierung von DFAs
Frage
Wie können wir feststellen, ob ein DFA M ❼Z , Σ, δ, q0 , E ➁ eine minimale
Anzahl von Zuständen besitzt (und Z evtl. verkleinern)?
Beispiel
▲
Betrachte den DFA M
b
1
a
2
b
a
a
a
b
b
5
4
b
b
b
a
6
b
▲
a
3
a
7
a
8
Zunächst können alle vom Startzustand aus unerreichbaren Zustände
entfernt werden.
❘
Minimierung von DFAs
109
Frage
Wie können wir feststellen, ob ein DFA M ❼Z , Σ, δ, q0 , E ➁ eine minimale
Anzahl von Zuständen besitzt (und Z evtl. verkleinern)?
Antwort
▲
▲
▲
Zunächst können alle vom Startzustand aus unerreichbaren Zustände
entfernt werden.
Zudem lassen sich zwei Zustände p und q verschmelzen, wenn
M von p und q aus jeweils dieselben Wörter akzeptiert.
Für z ❃ Z sei
Mz ❼Z , Σ, δ, z, E ➁.
▲
▲
Dann können wir p und q verschmelzen (in Zeichen: p ✂ q), wenn
L❼Mp ➁ L❼Mq ➁ ist.
Offensichtlich ist ✂ eine Äquivalenzrelation auf Z .
110
Minimierung von DFAs
Idee
Verschmelze jeden Zustand z mit allen äquivalenten Zuständen z ✂ z zu
einem neuen Zustand.
➐
Notation
▲
Für die durch z repräsentierte Äquivalenzklasse
z ✆✂
➌z ❃ Z ❙ z ✂ z ➑ ➌z ❃ Z ❙ L❼Mz ➐ ➁ L❼Mz ➁➑
➐
➐
➐
schreiben wir auch einfach z ✆ oder z˜.
▲
Für eine Teilmenge Q ❜ Z bezeichne
˜ ➌q˜ ❙ q ❃ Q ➑
Q
die Menge aller Äquivalenzklassen q˜, die mind. ein q ❃ Q enthalten.
▲
Dann führt obige Idee auf folgenden DFA:
M ❼Z˜ , Σ, δ , q˜0 , E˜ ➁ mit δ ❼q˜, a➁ δ❐
❼q, a➁.
➐
➐
➐
111
Wie können wir M aus M konstruieren?
➐
Hierzu genügt es, herauszufinden, ob zwei Zustände p und q von M
äquivalent sind oder nicht?
▲
Sei A∆B ❼A ✓ B ➁ ✽ ❼B ✓ A➁ die symmetrische Differenz von A und B.
▲
Die Inäquivalenz p ✂⑦ q ist also gleichbedeutend mit L❼Mp ➁∆L❼Mq ➁ ① ❣.
▲
▲
▲
▲
Wir nennen ein Wort x ❃ L❼Mp ➁∆L❼Mq ➁ einen Unterscheider zwischen
p und q.
Offenbar unterscheidet ε Zustände p ❃ E von Zuständen q ❃ Z
✓
E.
Falls x die Zustände δ ❼p, a➁ und δ ❼q, a➁ unterscheidet, so unterscheidet
ax die Zustände p und q, d.h. δ ❼p, a➁ ✂⑦ δ ❼q, a➁ p ✂⑦ q.
✟
Wenn also D nur inäquivalente Zustandspaare enthält, so trifft dies
auch auf die Menge
D ➌➌p, q ➑ ❙ ➜a ❃ Σ ✂ ➌δ ❼p, a➁, δ ❼q, a➁➑ ❃ D ➑
➐
zu.
112
Minimierung von DFAs
Satz
Sei M ❼Z , Σ, δ, q0 , E ➁ ein DFA ohne unerreichbare Zustände. Dann ist
M ❼Z˜ , Σ, δ , q˜0 , E˜ ➁ mit δ ❼q˜, a➁ δ❐
❼q, a➁
➐
➐
➐
ein DFA für L❼M ➁ mit einer minimalen Anzahl von Zuständen.
Beweis
▲
▲
▲
Zuerst müssen wir zeigen, dass δ wohldefiniert ist, also δ ❼q˜, a➁ nicht
von der Wahl des Repräsentanten q für die Äquivalenzklasse q˜ abhängt.
➐
Hierzu ist die Implikation p ✂ q
✟ δ❼p, a➁ ✂ δ❼q, a➁ zu zeigen.
Diese ist wiederum äquivalent zur Kontraposition
δ ❼p, a➁ ✂⑦ δ ❼q, a➁ p ✂⑦ q, die wir bereits gezeigt haben.
✟
➐
113
Minimierung von DFAs
Satz
Sei M ❼Z , Σ, δ, q0 , E ➁ ein DFA ohne unerreichbare Zustände. Dann ist
M ❼Z˜ , Σ, δ , q˜0 , E˜ ➁ mit δ ❼q˜, a➁ δ❐
❼q, a➁
➐
➐
➐
ein DFA für L❼M ➁ mit einer minimalen Anzahl von Zuständen.
Beweis (Fortsetzung)
▲
▲
Als nächstes zeigen wir, dass L❼M
➐
➁
L❼M ➁ ist.
Sei x x1 . . . xn ❃ Σ eine Eingabe und seien q0 , q1 , . . . , qn die von M ❼x ➁
durchlaufenen Zustände, d.h. es gilt δ ❼qi 1 , xi ➁ qi für i 1, . . . , n.
❻
✏
▲
Nach Definition von δ folgt daher δ ❼q˜i 1 , xi ➁ q˜i für i 1, . . . , n,
d.h. M durchläuft bei Eingabe x die Zustände q˜0 , q˜1 , . . . , q˜n .
➐
➐
✏
➐
▲
Da aber q˜n entweder nur End- oder nur Nicht-Endzustände enthält,
gehört qn genau dann zu E , wenn q˜n ❃ E˜ , d.h. es gilt
x ❃ L❼M ➁
✔ x ❃ L❼M ➁.
➐
114
Minimierung von DFAs
Beweis (Schluss)
▲
▲
▲
Noch z.z.: die Anzahl ❨Z˜ ❨ der Zustände von M ist minimal.
Wegen ❨Z˜ ❨ ❇ ❨Z ❨ ist M sicher dann minimal, wenn M minimal ist.
Es reicht also zu zeigen, dass ❨Z˜ ❨ nur von der Sprache L❼M ➁ abhängt.
➐
➐
✔ L❼Mp ➁ L❼Mq ➁ gilt ❨Z˜ ❨ ❨➌L❼Mz ➁ ❙ z ❃ Z ➑❨.
▲
Wegen p ✂ q
▲
Sei L L❼M ➁ und für x ❃ Σ sei Lx die Sprache ➌y ❃ Σ
▲
❻
❻
❙
xy ❃ L➑.
Dann gilt ➌Lx ❙ x ❃ Σ ➑ ➌L❼Mz ➁ ❙ z ❃ Z ➑:
❜: Klar, da Lx L❼Mz ➁ für z δˆ❼q0 , x ➁ ist.
❻
❝: Auch klar, da jedes z ❃ Z über ein x ❃ Σ erreichbar ist.
Also hängt ❨Z˜ ❨ ❨➌Lx ❙ x ❃ Σ ➑❨ nur von L ab.
❻
▲
❻
❥
Bemerkung
Der Beweis zeigt, dass folgende Äquivalenzrelation RL endlichen Index hat:
x RL y ✂
Lx Ly .
✔
115
Wie können wir M aus M berechnen?
➐
Hierzu genügt es, zu entscheiden, ob zwei Zustände p und q von M
äquivalent sind oder nicht?
▲
▲
▲
Offenbar unterscheidet ε Zustände p ❃ E von Zuständen q ❃ Z
✓
E.
Falls x die Zustände δ ❼p, a➁ und δ ❼q, a➁ unterscheidet, so unterscheidet
ax die Zustände p und q, d.h. δ ❼p, a➁ ✂⑦ δ ❼q, a➁ p ✂⑦ q.
✟
Wenn also D nur inäquivalente Zustandspaare enthält, so trifft dies
auch auf die Menge
D ➌➌p, q ➑ ❙ ➜a ❃ Σ ✂ ➌δ ❼p, a➁, δ ❼q, a➁➑ ❃ D ➑
➐
zu.
Algorithmische Konstruktion von M
➐
Idee
▲
Berechne ausgehend von D0 ➌➌p, q ➑ ❙ p ❃ E , q ❃⑦ E ➑ mittels
Di
✔
1
Di ✽ ➌➌p, q ➑ ❙ ➜a ❃ Σ ✂ ➌δ ❼p, a➁, δ ❼q, a➁➑ ❃ Di ➑
eine Folge D0 ❜ D1 ❜ D2 ❜ ✆ von Mengen mit inäquivalenten
Zustandspaaren.
▲
Da es nur endlich viele Zustandspaare gibt, muss es ein j geben mit
Dj 1 Dj .
✔
▲
Für die Menge D Dj gilt dann
p ✂⑦ q
▲
✔ ➌p, q➑ ❃ D
(siehe Übungen).
Folglich gilt
z˜ ➌z ❃ Z
➐
❙ ➌z, z ➑ ❃
⑦
➐
D ➑.
116
Algorithmus zur Berechnung eines minimalen DFA
Algorithmus min-DFA❼M ➁
1
Input: DFA M ❼Z , Σ, δ, q0 , E ➁
2
3
4
5
6
7
8
entferne alle nicht erreichbaren Zustände
D ✂ ➌➌z, z ➑ ❙ z ❃ E , z ❃⑦ E ➑
repeat
D ✂ D
D ✂ D ✽ ➌➌p, q ➑ ❙ ➜a ❃ Σ ✂ ➌δ ❼p, a➁, δ ❼q, a➁➑ ❃ D ➑
until D D
Output: M ❼Z˜ , Σ, δ , q˜0 , E˜ ➁, wobei für jeden Zustand
z ❃ Z gilt: z˜ ➌z ❃ Z ❙ ➌z, z ➑ ❃⑦ D ➑
➐
➐
➐
➐
➐
➐
➐
➐
➐
➐
117
Algorithmus für die Konstruktion von M
118
➐
Beispiel
Betrachte den DFA M
b
2
a
3
b
a
4
a
a
b
b
1
a
6
b
b
a
5
2
3 ε ε
4
ε
5
ε
6 ε ε
ε ε
1 2 3 4 5
Dann enthält D0 die Paare
➌1, 3➑, ➌1, 6➑, ➌2, 3➑, ➌2, 6➑, ➌3, 4➑, ➌3, 5➑, ➌4, 6➑, ➌5, 6➑.
Algorithmus für die Konstruktion von M
119
➐
Beispiel
Betrachte den DFA M
b
2
3
b
a
4
a
a
b
b
1
2
3
4
5
6
a
b
a
6
b
a
5
ε
a
a
ε
ε
a ε
a ε
ε
ε ε
1 2 3 4 5
Wegen
➌p, q ➑
➌1, 4➑
➌1, 5➑
➌2, 4➑
➌2, 5➑
➌δ ❼q, a➁, δ ❼p, a➁➑
➌2, 3➑
➌2, 6➑
➌1, 3➑
➌1, 6➑
enthält D1 zusätzlich die Paare ➌1, 4➑, ➌1, 5➑, ➌2, 4➑, ➌2, 5➑.
Algorithmus für die Konstruktion von M
120
➐
Beispiel
Betrachte den DFA M
b
2
3
b
a
4
a
a
b
b
1
2
3
4
5
6
a
b
a
6
b
a
5
ε
a
a
ε
ε
a ε
a ε
ε
ε ε
1 2 3 4 5
Da nun jedoch die verbliebenen Paare ➌1, 2➑, ➌3, 6➑, ➌4, 5➑ wegen
➌p, q ➑
➌1, 2➑
➌3, 6➑
➌4, 5➑
➌δ ❼p, a➁, δ ❼q, a➁➑
➌1, 2➑
➌4, 5➑
➌3, 6➑
➌δ ❼p, b ➁, δ ❼q, b ➁➑
➌3, 6➑
➌1, 2➑
➌4, 5➑
nicht zu D1 hinzugefügt werden können, ist D2 D1 D.
Algorithmus für die Konstruktion von M
121
➐
Beispiel
Betrachte den DFA M
b
2
3
b
a
2
3
4
5
6
a
4
a
a
b
b
b
a
1
6
b
5
a
ε
a
a
ε
ε
a ε
a ε
ε
ε ε
1 2 3 4 5
Da die Paare ➌1, 2➑, ➌3, 6➑ und ➌4, 5➑ nicht in D enthalten sind, können
die Zustände 1 und 2, 3 und 6, sowie 4 und 5 verschmolzen werden.
Demnach hat M die Zustände ˜
1 ➌1, 2➑, ˜
3 ➌3, 6➑ und ˜4 ➌4, 5➑:
➐
b
˜
1
b
a
a
˜
3
a
˜
4
b
❘
Document
Kategorie
Gesundheitswesen
Seitenansichten
9
Dateigröße
303 KB
Tags
1/--Seiten
melden