close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

22.Oktober

EinbettenHerunterladen
36
Eigenschaften von NFAs
Beobachtung 6
Ist N ❼Z , Σ, ∆, Q0 , E ➁ ein NFA, so wird auch die Sprache L❼N ➁ von
❻
einem NFA erkannt.
Beweis
Die Sprache L❼N ➁ wird von dem NFA
❻
N ❼Z ✽➌qneu ➑, Σ, ∆ , Q0 ✽➌qneu ➑, E ✽➌qneu ➑➁
➐
➐
mit
∆ ❼p, a➁ ➐
erkannt.
➣
➝
∆❼p, a➁,
➝
➝
➝
➝
➛∆❼p, a➁ ✽
➝
➝
➝
➝
➝
↕❣ ,
✣q❃Q
p❃Z
0
✓
E,
∆❼q, a➁, p ❃ E ,
p qneu
❥
Überblick
Ziel
Zeige, dass REG unter Produktbildung und Sternhülle abgeschlossen ist.
Problem
Bei der Konstruktion eines DFA für das Produkt L1 L2 bereitet es
Schwierigkeiten, den richtigen Zeitpunkt für den Übergang von (der
Simulation von) M1 zu M2 zu finden.
Lösungsidee (bereits umgesetzt)
Ein nichtdeterministischer Automat (NFA) kann den richtigen Zeitpunkt
für den Übergang „raten“.
Noch zu zeigen
NFAs erkennen genau die regulären Sprachen.
37
NFAs erkennen genau die regulären Sprachen
38
Satz (Rabin und Scott)
REG ➌L❼N ➁ ❙ N ist ein NFA➑.
Beweis von REG ❜ ➌L❼N ➁ ❙ N ist ein NFA➑
Diese Inklusion ist klar, da jeder DFA M ❼Z , Σ, δ, q0 , E ➁ leicht in einen
äquivalenten NFA
N ❼Z , Σ, ∆, Q0 , E ➁
transformiert werden kann, indem wir ∆❼q, a➁ ➌δ ❼q, a➁➑ und Q0 ➌q0 ➑
setzen.
❥
Für die umgekehrte Inklusion ist das Erreichbarkeitsproblem für NFAs von
zentraler Bedeutung.
Das Erreichbarkeitsproblem für NFAs
39
Frage
Sei N ❼Z , Σ, ∆, Q0 , E ➁ ein NFA und sei x x1 . . . xn eine Eingabe. Welche
Zustände sind in i Schritten erreichbar?
Antwort
▲
in 0 Schritten: alle Zustände in Q0 .
▲
in einem Schritt: alle Zustände in
Q1 ▲
✤
q ❃Q0
∆❼q, x1 ➁.
in i Schritten: alle Zustände in
Qi ✤
q ❃Qi ✏1
∆❼q, xi ➁.
40
Simulation von NFAs durch DFAs
Idee
▲
Wir können einen NFA N ❼Z , Σ, ∆, Q0 , E ➁ durch einen DFA
M ❼Z , Σ, δ, q0 , E ➁ simulieren, der in seinem Zustand die Information
speichert, in welchen Zuständen sich N momentan befinden könnte.
➐
▲
➐
➐
Die Zustände von M sind also Teilmengen Q von Z (d.h. Z P ❼Z ➁)
mit Q0 als Startzustand (d.h. q0 Q0 ) und der Endzustandsmenge
➐
➐
E ➌Q ❜ Z ❙ Q ✾ E ⑦ ❣➑.
➐
▲
Die Überführungsfunktion δ ✂ P ❼Z ➁ ✕ Σ P ❼Z ➁ von M berechnet dann
für einen Zustand Q ❜ Z und ein Zeichen a ❃ Σ die Menge
δ ❼Q, a➁ ✤ q❃Q ∆❼q, a➁
aller Zustände, in die N gelangen kann, wenn N ausgehend von einem
beliebigen Zustand q ❃ Q das Zeichen a liest.
41
Simulation von NFAs durch DFAs
Beispiel
▲
Betrachte den NFA N
0
p
q
1
r
2
s
0, 1, 2
▲
Ausgehend von Q0 ➌p ➑ liefert δ dann die folgenden Werte:
1, 2
δ
0
1
0
2
➌
➌p ➑
➌p, q ➑
➌p ➑
➌p, q ➑
➌p, q ➑
➌p, r ➑
➌p ➑
➌p, r ➑
➌p, q ➑
➌p ➑
➌p, s ➑
➌p, s ➑
➌p, q ➑
➌p ➑
➌p ➑
0
p➑
p, q ➑
➌
➌p ➑
2
1, 2
0
0
1
1
p, s ➑
➌
2
p, r ➑
➌
❘
Simulation von NFAs durch DFAs
42
Bemerkung
▲
Im obigen Beispiel werden für die Konstruktion des Potenzmengenautomaten nur 4 der insgesamt
❨P ❼Z ➁❨
2❨Z ❨ 24 16
Zustände benötigt, da die übrigen 12 Zustände nicht erreichbar sind.
▲
Es gibt jedoch Beispiele, bei denen alle 2❨Z ❨ Zustände benötigt werden
(siehe Übungen).
43
NFAs erkennen genau die regulären Sprachen
Beweis von ➌L❼N ➁ ❙ N ist ein NFA➑ ❜ REG
▲
Sei N ❼Z , Σ, ∆, Q0 , E ➁ ein NFA und sei M ❼P ❼Z ➁, Σ, δ, Q0 , E ➁ der
zugehörige Potenzmengenautomat mit δ ❼Q, a➁ ✣q❃Q ∆❼q, a➁ und
E ➌Q ❜ Z ❙ Q ✾ E ⑦ ❣➑.
➐
➐
▲
Dann folgt die Korrektheit von M leicht mittels folgender Behauptung,
die wir auf der nächsten Folie beweisen.
Behauptung
▲
δˆ❼Q0 , x ➁ enthält genau die von N nach Lesen von x erreichbaren
Zustände.
Für alle Wörter x ❃ Σ gilt
❻
x ❃ L❼N ➁
✔
✔
✔
✔
Beh.
N kann nach Lesen von x einen Endzustand erreichen
δˆ❼Q0 , x ➁ ✾ E ⑦ ❣
δˆ❼Q0 , x ➁ ❃ E
x ❃ L❼M ➁.
➐
❥
44
Beweis der Behauptung
Behauptung
δˆ❼Q0 , x ➁ enthält genau die von N nach Lesen von x erreichbaren Zustände.
Beweis durch Induktion über die Länge n von x
n 0: klar, da δˆ❼Q0 , ε➁ Q0 ist.
n✏1
➔ n:
Sei x x1 . . . xn gegeben. Nach IV enthält
Qn 1 δˆ❼Q0 , x1 . . . xn 1 ➁
✏
✏
die Zustände, die N nach Lesen von x1 . . . xn
kann. Wegen
δˆ❼Q0 , x ➁ δ ❼Qn 1 , xn ➁ ✤ ∆❼q, xn ➁
✏
✏
1
erreichen
q ❃Qn✏1
enthält dann aber δˆ❼Q0 , x ➁ die Zustände, die N nach Lesen
von x erreichen kann.
❥
Abschlusseigenschaften der Klasse REG
Korollar
Die Klasse REG der regulären Sprachen ist unter folgenden Operationen
abgeschlossen:
▲
Komplement,
▲
Schnitt,
▲
Vereinigung,
▲
Produkt,
▲
Sternhülle.
45
Überblick
Nächstes Ziel
Zeige, dass REG als Abschluss der endl. Sprachen unter Vereinigung,
Produkt und Sternhülle charakterisierbar ist.
Bereits gezeigt:
Jede Sprache, die mittels der Operationen Vereinigung, Produkt und
Sternhülle (sowie Schnitt und Komplement) angewandt auf endliche
Sprachen darstellbar ist, ist regulär.
Noch zu zeigen:
Jede reguläre Sprache lässt sich aus endlichen Sprachen mittels
Vereinigung, Produkt und Sternhülle erzeugen.
46
47
Konstruktive Charakterisierung von REG
Induktive Definition der Menge RAΣ aller regulären Ausdrücke über Σ
Die Symbole ❣, und a (a ❃ Σ) sind reguläre Ausdrücke über Σ, die
die leere Sprache L❼❣➁ ❣,
die Sprache L❼ ➁ ➌ε➑ und
für jedes a ❃ Σ die Sprache L❼a➁ ➌a➑ beschreiben.
▲
▲
▲
Sind α und β reguläre Ausdrücke über Σ, die die Sprachen L❼α➁ und L❼β ➁
beschreiben, so sind auch αβ, ❼α❙β ➁ und ❼α➁ reguläre Ausdrücke über Σ,
die folgende Sprachen beschreiben:
❻
▲
L❼αβ ➁ L❼α➁L❼β ➁,
▲
L❼α❙β ➁ L❼α➁ ✽ L❼β ➁,
▲
L❼❼α➁
❻
➁
L❼α➁ .
❻
Bemerkung
RAΣ ist eine Sprache über dem Alphabet Γ Σ ✽ ➌❣, , ❙, ✽, , ❼, ➁➑.
❻
48
Reguläre Ausdrücke
Beispiel
Die regulären Ausdrücke
folgende Sprachen:
γ
❼ ➁❻
❼❣ ➁❻
L❼γ ➁
➌ ε➑
➌ε➑
❼ ➁❻ , ❼❣➁❻ , ❼0❙1➁❻ 00
❼0❙1➁❻ 00
➌x 00 ❙
x ❃ ➌0, 1➑
und
❼0❙❼
❻
❼
0❙❣❼1➁
0❙❣❼1➁
➑
❻
❻
➁
beschreiben
➁➁
➌0➑
❘
Vereinbarungen
▲
Um Klammern zu sparen, definieren wir folgende Präzedenzordnung:
Der Sternoperator bindet stärker als der Produktoperator und dieser
wiederum stärker als der Vereinigungsoperator.
❻
▲
▲
Für ❼0❙❼ 0❙❣❼1➁
❻
➁➁
können wir also kurz 0❙ 0❙❣1 schreiben.
❻
Da der reguläre Ausdruck γγ die Sprache L❼γ ➁ beschreibt, verwenden
wir γ als Abkürzung für den Ausdruck γγ .
❻
✔
✔
❻
Charakterisierung von REG durch reguläre Ausdrücke
Satz
➌L❼γ ➁ ❙
49
γ ist ein regulärer Ausdruck über Σ➑ ❜ REG.
Beweis.
Klar, da
▲
▲
die Basisausdrücke
beschreiben und
,
❣
und a, a ❃ Σ , nur reguläre Sprachen
❻
die Sprachklasse REG unter Produkt, Vereinigung und Sternhülle
abgeschlossen ist.
❥
Charakterisierung von REG durch reguläre Ausdrücke
M3 :
Frage
0
Wie lässt sich die Sprache
a
a
L❼M3 ➁ ➌x ❃ ➌a, b ➑
b
b
b
2
50
1
❻
❙
#a ❼x ➁ ✏ #b ❼x ➁ ✁3 1➑
durch einen regulären Ausdruck beschreiben?
a
Antwort
▲
▲
▲
Sei Lp,q die Sprache aller Wörter x , die M3 vom Zustand p in den
Zustand q überführen (d.h. δˆ❼p, x ➁ q).
r
Weiter sei L①p,q
die Sprache aller Wörter x x1 ✆xn ❃ Lp,q , die hierzu nur
Zustände ungleich r benutzen (d.h. δˆ❼p, x1 ✆xi ➁ ① r für i 1, . . . , n ✏ 1).
0
0
Dann gilt L❼M3 ➁ L0,1 L0,0 L①0,1
und L0,0 ❼L①0,0
➁ , also
①
0
①
0
L❼M3 ➁ ❼L0,0 ➁ L0,1 .
❻
❻
Charakterisierung von REG durch reguläre Ausdrücke
51
Antwort (Fortsetzung)
▲
M3 :
0
▲
a
a
b
b
0
0
L①0,1
und L①0,0
lassen sich durch folgende
reguläre Ausdrücke beschreiben:
❻
①0 a❼ab ➁ ❼aa❙b ➁ ❙ b ❼ba➁ ❼a❙bb ➁ ❙ ε.
γ0,0
❻
1
a
▲
❻
①0 ❼a❙bb ➁❼ab ➁ ,
γ0,1
b
2
0
0
Dann gilt L❼M3 ➁ ❼L①0,0
➁ L①
0,1 .
❻
Also ist L❼M3 ➁ durch folgenden regulären Ausdruck beschreibbar:
γ0,1 ❼a❼ab ➁ ❼aa❙b ➁ ❙ b ❼ba➁ ❼a❙bb ➁➁ ❼a❙bb ➁❼ab ➁ .
❻
❻
❻
❻
Charakterisierung von REG durch reguläre Ausdrücke
Satz
REG ❜ ➌L❼γ ➁ ❙ γ ist ein regulärer Ausdruck➑.
Beweis
▲
Wir konstruieren zu einem DFA M ❼Z , Σ, δ, q0 , E ➁ einen regulären
Ausdruck γ mit L❼γ ➁ L❼M ➁.
▲
Wir nehmen an, dass Z ➌1, . . . , m➑ und q0 1 ist.
▲
Dann lässt sich L❼M ➁ als Vereinigung
L❼M ➁ ✤ L1,q
q ❃E
von Sprachen der Form Lp,q ➌x ❃ Σ
▲
❻
ˆ❼p, x ➁
❙δ
q ➑ darstellen.
Es reicht also, reguläre Ausdrücke für die Sprachen Lp,q mit
1 ❇ p, q ❇ m anzugeben.
52
Charakterisierung von REG durch reguläre Ausdrücke
Satz
REG ❜ ➌L❼γ ➁ ❙ γ ist ein regulärer Ausdruck➑.
Beweis (Fortsetzung)
▲
▲
Es reicht also, reguläre Ausdrücke für die Sprachen Lp,q mit
1 ❇ p, q ❇ m anzugeben.
Hierzu betrachten wir für r 0, . . . , m die Sprachen
Lrp,q ➍x ❃ Lp,q für i 1, . . . , n ✏ 1 ist δˆ❼p, x1 . . . xi ➁ ❇ r ➒ .
▲
▲
r
Wegen Lp,q Lm
p,q reicht es, reguläre Ausdrücke für die Sprachen Lp,q
mit 1 ❇ p, q ❇ m und 0 ❇ r ❇ m anzugeben.
Wir zeigen induktiv über r , dass die Sprachen Lrp,q durch reguläre
Ausdrücke beschreibbar sind.
53
Charakterisierung von REG durch reguläre Ausdrücke
54
Satz
REG ❜ ➌L❼γ ➁ ❙ γ ist ein regulärer Ausdruck➑.
Beweis (Schluss)
▲
Wir zeigen induktiv über r , dass die Sprachen Lrp,q durch reguläre
Ausdrücke beschreibbar sind.
r 0: In diesem Fall sind die Sprachen
➣
➝
➝➌ a
L0p,q ➛
➝
➝
↕➌ a
r
➔r
✔
❃ Σ ❙ δ ❼p, a➁ q ➑,
p ① q,
❃ Σ ❙ δ ❼p, a➁ q ➑ ✽ ➌ε➑, sonst
endlich und somit durch reguläre Ausdrücke beschreibbar.
1: Wegen
Lrp,q1 Lrp,q ✽ Lrp,r
✔
✔
r
❻
r
1 ❼Lr ✔1,r ✔1 ➁ Lr ✔1,q
sind mit Lrp,q , 1 ❇ p, q ❇ m, auch die Sprachen Lrp,q1 ,
1 ❇ p, q ❇ m, durch reguläre Ausdrücke beschreibbar.
✔
❥
Document
Kategorie
Gesundheitswesen
Seitenansichten
9
Dateigröße
292 KB
Tags
1/--Seiten
melden