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 L Betrachte den DFA M b 1 a 2 b a a a b b 5 4 b b b a 6 b L a 3 a 7 a 8 Zunächst können alle vom Startzustand aus unerreichbaren Zustände entfernt werden. R 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 L L L 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 L L Z , Σ, δ, z, E . Dann können wir p und q verschmelzen (in Zeichen: p q), wenn LMp LMq 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 L Für die durch z repräsentierte Äquivalenzklasse z z > Z S z z z > Z S LMz LMz schreiben wir auch einfach z oder z̃. L Für eine Teilmenge Q b Z bezeichne q̃ S Q̃ q > Q die Menge aller Äquivalenzklassen q̃, die mind. ein q > Q enthalten. L Dann führt obige Idee auf folgenden DFA: M Z̃ , Σ, δ , q̃0 , Ẽ 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? A B 8 B A die symmetrische Differenz von A und B. L Sei A∆B L Die Inäquivalenz p ~ q ist also gleichbedeutend mit LMp ∆LMq x g. L L L L Wir nennen ein Wort x > LMp ∆LMq 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 zu. p, q S § a > Σ δ p, a, δ q, a > D 112 Minimierung von DFAs Satz Z , Σ, δ, q0 , E Sei M M Z̃ , Σ, δ ein DFA ohne unerreichbare Zustände. Dann ist , q̃0 , Ẽ mit δ q̃, a δË q, a ein DFA für LM mit einer minimalen Anzahl von Zuständen. Beweis L L L 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 Z , Σ, δ, q0 , E Sei M M Z̃ , Σ, δ ein DFA ohne unerreichbare Zustände. Dann ist , q̃0 , Ẽ mit δ q̃, a δË q, a ein DFA für LM mit einer minimalen Anzahl von Zuständen. Beweis (Fortsetzung) L L Als nächstes zeigen wir, dass LM LM 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. L 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 . L Da aber q̃n entweder nur End- oder nur Nicht-Endzustände enthält, gehört qn genau dann zu E , wenn q̃n > Ẽ , d.h. es gilt x > LM x > LM . 114 Minimierung von DFAs Beweis (Schluss) L Noch z.z.: die Anzahl YZ̃ Y der Zustände von M ist minimal. L Wegen YZ̃ Y B YZ Y ist M sicher dann minimal, wenn M minimal ist. L Es reicht also zu zeigen, dass YZ̃ Y nur von der Sprache LM abhängt. L Wegen p q L L Sei L LMp LMq gilt YZ̃ Y YLMz S z > Z Y. LM und für x > Σ sei Lx die Sprache y > Σ S xy > L. Dann gilt Lx S x > Σ LMz S z > Z : b: Klar, da Lx LMz für z δ̂ q0 , x ist. c: Auch klar, da jedes z > Z über ein x > Σ erreichbar ist. Also hängt YZ̃ Y YLx S x > Σ Y nur von L ab. L j 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? L L L 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 zu. p, q S § a > Σ δ p, a, δ q, a > D Algorithmische Konstruktion von M Idee L Berechne ausgehend von D0 Di Di 1 8 p, q S § p, q S p > E , q >~ E mittels a > Σ δ p, a, δ q, a > Di eine Folge D0 b D1 b D2 b von Mengen mit inäquivalenten Zustandspaaren. L Da es nur endlich viele Zustandspaare gibt, muss es ein j geben mit Dj 1 Dj . L Für die Menge D p ~ q L Dj gilt dann p, q > D (siehe Übungen). Folglich gilt z̃ z >Z S z, z > ~ D . 116 Algorithmus zur Berechnung eines minimalen DFA Algorithmus min-DFAM 1 2 3 4 5 6 7 8 Input: DFA M Z , Σ, δ, q0 , E entferne alle nicht erreichbaren Zustände D z, z S z > E , z >~ E repeat D D D D 8 p, q S §a > Σ δ p, a, δ q, a > D until D D Output: M Z̃ , Σ, δ , q̃0 , Ẽ , wobei für jeden Zustand z > Z gilt: z̃ z > Z S 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̃ 3̃ b a a a 4̃ b R
© Copyright 2024 ExpyDoc
