close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

20.Oktober

EinbettenHerunterladen
Die Klasse der regulären Sprachen
21
Definition
Eine von einem DFA akzeptierte Sprache wird als regulär bezeichnet. Die
zugehörige Sprachklasse ist
REG ➌L❼M ➁ ❙ M ist ein DFA➑.
Frage
Welche Sprachen gehören zu REG und welche nicht?
22
Singletons sind regulär
Vereinbarung
Für das Folgende sei Σ ➌a1 , . . . , am ➑ ein fest gewähltes Alphabet.
Beobachtung 1
Alle Sprachen, die nur ein Wort x x1 . . . xn ❃ Σ❻ enthalten, sind regulär.
Beweis
Folgender DFA M erkennt die Sprache L❼M ➁ ➌x ➑:
x1
q0
a ① x1
x2
q1
q2
a ① x2
x3
a ① x3
✆
xn
qn
a❃Σ
e
a❃Σ
❥
Abschlusseigenschaften von Sprachklassen
23
Definition
▲ Ein (k-stelliger) Sprachoperator ist eine Abbildung op, die k Sprachen
L1 , . . . , Lk auf eine Sprache op ❼L1 , . . . , Lk ➁ abbildet.
▲ Eine Sprachklasse ❑ heißt unter op abgeschlossen, wenn gilt:
L1 , . . . , Lk ❃ ❑
✟ op L1, . . . , Lk
❼
➁
❃ ❑.
▲ Der Abschluss von ❑ unter op ist die (bzgl. Inklusion) kleinste
Sprachklasse ❑➐ , die ❑ enthält und unter op abgeschlossen ist.
Beispiel
▲ Der 2-stellige Schnittoperator
✾
bildet L1 und L2 auf L1 ✾ L2 ab.
▲ Der Abschluss der Singletonsprachen unter
✾
besteht aus allen
✽
besteht aus allen
Singletonsprachen und der leeren Sprache.
▲ Der Abschluss der Singletonsprachen unter
nichtleeren endlichen Sprachen.
❘
REG ist unter Komplement abgeschlossen
24
¯ ❙ L ❃ ❈ ➑ aller
▲ Für eine Sprachklasse ❈ bezeichne co-❈ die Klasse ➌L
Komplemente von Sprachen in ❈ .
▲ ❈ ist genau dann unter Komplementbildung abgeschlossen, wenn
co-❈ ❈ ist.
Beobachtung 2
Ist L ❃ REG, so ist auch die Sprache L Σ❻ ✓ L regulär.
Beweis
▲ Sei M ❼Z , Σ, δ, q0 , E ➁ ein DFA mit L❼M ➁ L.
▲ Dann akzeptiert der DFA
M ❼Z , Σ, δ, q0 , Z
✓
E➁
das Komplement L von L.
❥
REG ist unter Schnitt abgeschlossen
25
Beobachtung 3
Sind L1 , L2 ❃ REG, so ist auch die Sprache L1 ✾ L2 regulär.
Beweis
▲ Seien Mi ❼Zi , Σ, δi , qi , Ei ➁, i 1, 2, DFAs mit L❼Mi ➁ Li .
▲ Dann wird der Schnitt L1 ✾ L2 von dem DFA
M ❼Z1 ✕ Z2 , Σ, δ, ❼q1 , q2 ➁, E1 ✕ E2 ➁
mit
δ ❼❼p, q ➁, a➁ ❼δ1 ❼p, a➁, δ2 ❼q, a➁➁
erkannt.
▲ M wird auch als Kreuzproduktautomat bezeichnet.
❥
REG ist unter Vereinigung abgeschlossen
26
Beobachtung 4
Die Vereinigung L1 ✽ L2 von regulären Sprachen L1 und L2 ist regulär.
Beweis
Es gilt L1 ✽ L2 ❼L1 ✾ L2 ➁.
Frage
Wie sieht der zugehörige DFA aus?
Antwort
M ➐ ❼Z1 ✕ Z2 , Σ, δ, ❼q1 , q2 ➁, ❼E1 ✕ Z2 ➁ ✽ ❼Z1 ✕ E2 ➁➁.
❥
REG ist unter Mengenoperationen abgeschlossen
Korollar
Die Klasse REG der regulären Sprachen ist unter folgenden Operationen
abgeschlossen:
▲ Komplement,
▲ Schnitt,
▲ Vereinigung.
27
Wie umfangreich ist REG?
28
Folgerung
▲ Aus den Beobachtungen folgt, dass alle endlichen und alle co-endlichen
Sprachen regulär sind.
▲ Da die reguläre Sprache
L❼M3 ➁ ➌x ❃ ➌a, b ➑❻ ❙ #a ❼x ➁ ✏ #b ❼x ➁ ✁3 1➑
weder endlich noch co-endlich ist, haben wir damit allerdings noch
nicht alle regulären Sprachen erfasst.
Wie umfangreich ist REG?
Nächstes 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
Ein nichtdeterministischer Automat (NFA) kann den richtigen Zeitpunkt
für den Übergang „raten“.
Verbleibendes Problem
Zeige, dass auch NFAs nur reguläre Sprachen erkennen.
29
30
Nichtdeterministische endliche Automaten
Definition
▲ Ein nichtdet. endl. Automat (kurz: NFA; nondet. finite automaton)
N ❼Z , Σ, ∆, Q0 , E ➁
ist genau so aufgebaut wie ein DFA, nur dass er
eine Menge Q0 ❜ Z von Startzuständen hat und
die Überführungsfunktion folgende Form hat:
∆✂Z
✕
Σ
P
❼
Z ➁.
Hierbei bezeichnet P ❼Z ➁ die Potenzmenge (also die Menge aller
Teilmengen) von Z . Diese wird auch oft mit 2Z bezeichnet.
▲ Die von einem NFA N akzeptierte oder erkannte Sprache ist
L❼N ➁ ➐
x1 . . . xn ❃ Σ❻
q0 ❃ Q0 , q1 , . . . , qn✏1 ❃ Z , qn ❃ E ✂
qi ✔1 ❃ ∆❼qi , xi ✔1 ➁ für i 0, . . . , n ✏ 1
➜
q0 , q1 , . . . , qn heißt Rechnung von N ❼x1 . . . xn ➁, falls q0 ❃ Q0 und
qi ✔1 ❃ ∆❼qi , xi ✔1 ➁ für i 0, . . . , n ✏ 1 gilt.
→
.
Eigenschaften von NFAs
31
▲ Ein NFA N kann bei einer Eingabe x also nicht nur eine, sondern
mehrere verschiedene Rechnungen parallel ausführen.
▲ Ein Wort x gehört genau dann zu L❼N ➁, wenn N ❼x ➁ mindestens eine
akzeptierende Rechnung hat.
▲ Im Gegensatz zu einem DFA, der jede Eingabe zu Ende liest, kann ein
NFA N „stecken bleiben“.
▲ Dieser Fall tritt ein, wenn N in einen Zustand q gelangt, in dem er das
nächste Eingabezeichen xi wegen
∆❼q, xi ➁ ❣
nicht verarbeiten kann.
32
Eigenschaften von NFAs
Beispiel
▲ Betrachte den NFA N ❼Z , Σ, ∆, Q0 , E ➁ mit Z ➌p, q, r , s ➑,
Σ ➌0, 1, 2➑, Q0 ➌p ➑, E ➌s ➑ und der Überführungsfunktion
Graphische Darstellung:
∆
0
1
2
p
p, q ➑
➌p ➑
➌p ➑
➌
q
r
s
❣
❣
❣
p
r➑
➌
❣
❣
❣
s➑
❣
➌
0
q
1
r
2
s
0, 1, 2
▲ Dann ist L❼M ➁ ➌x 012 ❙ x ❃ Σ❻ ➑ die Sprache aller Wörter, die mit dem
Suffix 012 enden.
❘
33
Eigenschaften von NFAs
Beobachtung 5
Seien Ni ❼Zi , Σ, ∆i , Qi , Ei ➁ NFAs mit L❼Ni ➁ Li für i 1, 2. Dann wird
auch das Produkt L1 L2 von einem NFA erkannt.
Beweis
▲ Wir können Z1 ✾ Z2 ❣ annehmen.
▲ Dann gilt L❼N ➁ L1 L2 für den NFA N ❼Z1 ✽ Z2 , Σ, ∆, Q1 , E ➁ mit
➣
➝
➝
➝
➝
➝
➛
➝
➝
➝
➝
➝
↕
∆1 ❼p, a➁,
∆❼p, a➁ ∆1 ❼p, a➁ ✽ ✣q❃Q2 ∆2 ❼q, a➁,
∆2 ❼p, a➁,
und
E ➣
➝
➝
➛
➝
➝
↕
E2 ,
Q2 ✾ E2 ❣,
E1 ✽ E2 ,
sonst.
p ❃ Z1 ✓ E1 ,
p ❃ E1 ,
sonst
34
Eigenschaften von NFAs
▲ Dann gilt L❼N ➁ L1 L2 für den NFA N ❼Z1 ✽ Z2 , Σ, ∆, Q1 , E ➁ mit
➣
➝
➝
➝
➝
➝
➛
➝
➝
➝
➝
➝
↕
∆1 ❼p, a➁,
∆❼p, a➁ ∆1 ❼p, a➁ ✽ ✣q❃Q2 ∆2 ❼q, a➁,
∆2 ❼p, a➁,
p ❃ Z1 ✓ E1 ,
p ❃ E1 ,
sonst,
und E E2 , falls Q2 ✾ E2 ❣, bzw. E E1 ✽ E2 sonst.
Beweis von L1 L2 ❜ L❼N ➁:
▲ Seien x x1 ✆xk ❃ L1 , y y1 ✆yl ❃ L2 und seien q0 , . . . , qk und p0 , . . . , pl
akzeptierende Rechnungen von N1 ❼x ➁ und N2 ❼y ➁.
▲ Dann gilt q0 ❃ Q1 , qk ❃ E1 und p0 ❃ Q2 , pl ❃ E2 .
▲ Im Fall l ❈ 1 ist zudem p1 ❃ ∆2 ❼p0 , y1 ➁ und somit p1 ❃ ∆❼qk , y1 ➁.
▲ Im Fall l 0 ist zudem pl ❃ Q2 ✾ E2 und somit qk ❃ E .
▲ Also ist q0 , . . . , qk , p1 , . . . , pl eine akzeptierende Rechnung von N ❼xy ➁.
35
Eigenschaften von NFAs
▲ Dann gilt L❼N ➁ L1 L2 für den NFA N ❼Z1 ✽ Z2 , Σ, ∆, Q1 , E ➁ mit
➣
➝
➝
➝
➝
➝
➛
➝
➝
➝
➝
➝
↕
∆1 ❼p, a➁,
∆❼p, a➁ ∆1 ❼p, a➁ ✽ ✣q❃Q2 ∆2 ❼q, a➁,
∆2 ❼p, a➁,
p ❃ Z1 ✓ E1 ,
p ❃ E1 ,
sonst,
und E E2 , falls Q2 ✾ E2 ❣, bzw. E E1 ✽ E2 sonst.
Beweis von L❼N ➁ ❜ L1 L2 :
▲ Sei x x1 ✆xn ❃ L❼N ➁ und sei q0 , . . . , qn eine akz. Rechnung von N ❼x ➁.
▲ Dann gilt q0 ❃ Q1 , qn ❃ E , q0 , . . . , qi ❃ Z1 und qi ✔1 , . . . , qn ❃ Z2 für ein i.
▲ Im Fall i n ist qn ❃ E1 (d.h. x ❃ L1 ) und Q2 ✾ E2 ① ❣ (d.h. ε ❃ L2 ).
▲ Im Fall i ❅ n impliziert der Übergang qi ✔1 ❃ ∆❼qi , xi ✔1 ➁, dass qi ❃ E1
und qi ✔1 ❃ ∆2 ❼q, xi ✔1 ➁ für ein q ❃ Q2 ist.
▲ Also ist q0 , . . . , qi eine akz. Rechnung von N1 ❼x1 ✆xi ➁ und
q, qi ✔1 , . . . , qn eine akz. Rechnung von N2 ❼xi ✔1 ✆xn ➁, d.h. x ❃ L1 L2 .
❥
Document
Kategorie
Gesundheitswesen
Seitenansichten
8
Dateigröße
178 KB
Tags
1/--Seiten
melden