Endliche Automaten und reguläre Sprachen

Endliche Automaten und reguläre Sprachen
Endliche Automaten
1 / 151
Endliche Automaten
Endliche Automaten erlauben eine Beschreibung von Handlungsabläufen:
Wie ändert sich ein Systemzustand in Abhängigkeit von veränderten
Umgebungsbedingungen?
Vielfältiges Einsatzgebiet, nämlich:
- in der Definition der regulären Sprachen
also der Menge aller Folgen von Ereignissen,
die von einem Startzustand in einen gewünschten Zustand führen,
- in der Entwicklung digitaler Schaltungen
- in der Softwaretechnik (z. B. in der Modellierung des
Applikationsverhaltens)
- in der Compilierung: Lexikalische Analyse
- im Algorithmenentwurf für String Probleme
- in der Abstraktion tatsächlicher Automaten (wie Bank- und
Getränkeautomaten, Fahrstühle etc.)
Endliche Automaten
2 / 151
Das Problem der Flußüberquerung: Transitionssysteme
"Startzustand"
MWZ K
MZ
MZ
W K
M Z
M
M
MW K
Z
MW
K
MZ
MZ K
MK
MK
MW
MW Z
W
MZ
MZ
W
M WZ
MZ
K
MW
MK
MK
MW
Z
MW K
M
M
M
Z
W K
MZ
"akzeptierender Zustand"
M K Z
MZ
MWKZ
Dieser endliche Automat „akzeptiert“ genau diejenigen Folgen von einzelnen
Flussüberquerungen, die vom Startzustand in den akzeptierenden Zustand führen.
Endliche Automaten
Beispiele
3 / 151
Lexikalische Analyse
Zu Beginn liest der Compiler Anweisung nach Anweisung und bricht Anweisungen in
Tokenklassen auf.
Betrachte zum Beispiel die Anweisung
if distance >= rate * (end - start)
then distance = maxdistance;
mit den Tokenklassen:
- Keywords (für if und then),
- Variablen (für distance, rate, end, start, maxdistance),
- Operatoren (für *, -, =) und Vergleichsoperatoren (für >=),
- Klammern (für ( und )) und Semikolon (für ;).
Die lexikalische Analyse benutzt reguläre Grammatiken, bzw nichtdeterminische endliche
Automaten.
Endliche Automaten
Beispiele
4 / 151
Freischaltung eines Fernsehers
(1/2)
Um die Kindersicherung des Fernsehers über die Fernbedienung freizuschalten, muss
ein dreistelliger Code korrekt eingegeben werden. Dabei sind die folgenden Tasten
relevant:
- Die Tasten 0, . . . , 9,
- die Taste CODE sowie
- die Taste BACK.
Die Taste CODE muss vor Eingabe des Codes gedrückt werden.
Wird CODE während der Codeeingabe nochmals gedrückt, so wird die Eingabe neu
begonnen.
Wird BACK gedrückt, so wird die zuletzt eingegebene Zahl zurückgenommen.
Der Code zum Entsperren ist 999.
Endliche Automaten
Beispiele
5 / 151
Freischaltung eines Fernsehers
BACK
(2/2)
CODE
CODE
9
ready
9
BACK
CODE
CODE
0,...,8
9
BACK
0,...,8
BACK
CODE
CODE
99
9
ON
BACK
0,...,8
x
CODE
9x
0,...,9
0,...,9
BACK
xx
0,...,9
OFF
0,...,9
BACK
Der Automat „akzeptiert“ alle Folgen von Bedienoperationen,
die vom Zustand „ready“ in den Zustand „ON“ führen.
Endliche Automaten
Beispiele
6 / 151
Was ist ein endlicher Automat?
Ein deterministischer endlicher Automat (engl. deterministic finite automaton,
kurz DFA)
A = (Σ, Q, δ, q0 , F )
besteht aus:
einer endlichen Menge Σ, dem Eingabealphabet,
einer endlichen Menge Q, der Zustandsmenge (die Elemente aus Q werden
Zustände genannt),
einer Funktion δ von Q × Σ nach Q,
der Übergangsfunktion (oder Überführungsfunktion),
einem Zustand q0 ∈ Q, dem Startzustand,
sowie einer Menge F ⊆ Q von Endzuständen bzw. akzeptierenden
Zuständen. (Der Buchstabe F steht für „final states“, also „Endzustände“).
Endliche Automaten
DFAs: Die formale Definition
7 / 151
Das Zustandsdiagramm, bzw. der Automatengraph,
die grafische Darstellung eines DFA
Endliche Automaten
Der Automatengraph
8 / 151
Das Zustandsdiagramm, bzw. der Automatengraph
A = (Σ, Q, δ, q0 , F ) sei ein DFA.
Für jeden Zustand q ∈ Q gibt es einen durch
q
dargestellten Knoten.
Der Startzustand q0 wird durch einen in ihn hinein führenden Pfeil markiert,
d.h.:
q0
Jeder akzeptierende Zustand q ∈ F wird durch eine doppelte Umrandung
markiert, d.h.:
q
Seien p, q ∈ Q Zustände und a ∈ Σ ein Symbol des Alphabets mit
δ(q, a) = p. Dann füge einen mit dem Symbol a beschrifteten Pfeil von
Knoten
zu Knoten
ein, d.h.:
q
p
q
Endliche Automaten
a
Der Automatengraph
p
9 / 151
Wie arbeitet ein DFA?
Die erweiterte Übergangsfunktion
Endliche Automaten
Die erweiterte Übergangsfunktion
10 / 151
Wie arbeitet ein DFA A = (Σ, Q, δ, q0 , F )?
(1/2)
Ein DFA A = (Σ, Q, δ, q0 , F ) erhält als Eingabe ein Wort w ∈ Σ∗ ,
das eine Folge von „Aktionen“ oder „Bedienoperationen“ repräsentiert.
A wird im Startzustand q0 gestartet. Falls w das leere Wort ist, d.h. w = ε, dann
verbleibt A im Zustand q0 .
Also gelte w = a1 · · · an mit n ∈ N>0 und a1 , . . . , an ∈ Σ.
1. Der Automat liest den ersten Buchstaben a1 von w .
I
A wechselt in den Zustand q1 := δ(q0 , a1 ).
In der grafischen Darstellung von A wird der Zustand
q0
durch die mit a1 beschriftete Kante verlassen, und q1 ist der Endknoten dieser
Kante, d.h.
a1
q0
q1
Endliche Automaten
Die erweiterte Übergangsfunktion
11 / 151
Wie arbeitet ein DFA A = (Σ, Q, δ, q0 , F )?
(2/2)
2. Durch Lesen von a2 , dem zweiten Symbol von w , wechselt A in den Zustand
q2 := δ(q1 , a2 ).
In der grafischen Darstellung von A wird
q1
durch die mit a2 beschriftete Kante verlassen (falls diese Kante existiert)
a2
q1
q2
und der Automat landet in Zustand q2 = δ(q1 , a2 ).
n. Auf diese Weise wird das gesamte Eingabewort w = a1 · · · an abgearbeitet.
I
I
Ausgehend vom Startzustand q0 erreicht A nacheinander Zustände q1 , . . . , qn .
In der grafischen Darstellung von A entspricht diese Zustandsfolge einem Weg
der Länge n, der im Knoten
q0
startet und dessen Kanten mit den Buchstaben a1 , . . . , an beschriftet sind.
I
Schreibe δ(q0 , w ) := qn .
Endliche Automaten
Die erweiterte Übergangsfunktion
12 / 151
Was genau ist δ(q, w )?
Sei A := (Σ, Q, δ, q0 , F ) ein DFA. Die Funktion
δ : Q × Σ∗ → Q
ist rekursiv wie folgt definiert:
Der Rekursionsanfang: Für alle q ∈ Q ist δ(q, ε) := q.
Der Rekursionsschritt:
Für alle q ∈ Q, w ∈ Σ∗ und a ∈ Σ gilt für q 0 := δ(q, w ):
δ(q, wa) := δ(q 0 , a).
Insgesamt gilt: δ(q0 , w ) ist der durch Verarbeiten des Worts w erreichte Zustand.
Endliche Automaten
Die erweiterte Übergangsfunktion
13 / 151
DFAs: Die Maschinensichtweise
Verarbeitung eines Eingabeworts
durch einen DFA A:
w=
a1 a2 a3
···
Lesekopf
q0
aktueller
Zustand
Wir können uns einen DFA als eine Maschine vorstellen, die
∗ ihre Eingabe w = a1 a2 a3 · · · an
von links-nach-rechts mit Hilfe eines Lesekopfes durchläuft
∗ und dabei Zustandsübergänge durchführt.
Können wir heutige Rechner durch DFAs modellieren?
Endliche Automaten
DFAs: Die Maschinensichtweise
14 / 151
Die Sprache eines DFA
DFAs und ihre Sprachen
15 / 151
Wann akzeptiert A = (Σ, Q, δ, q0 , F ) ein Wort w ?
Das Eingabewort w wird vom DFA A akzeptiert, falls
δ(q0 , w ) ∈ F ,
d.h., der nach Verarbeiten von w erreichte Zustand gehört zur Menge F der
akzeptierenden Zustände.
Wie „übersetzt“ sich
Akzeptanz von w = a1 · · · an
in der grafischen Darstellung von A? Es gibt einen in
q0
startenden Weg der Länge n,
- dessen Kanten mit den Symbolen a1 , . . . , an beschriftet sind,
- und der in einem akzeptierenden Zustand
DFAs und ihre Sprachen
endet.
16 / 151
Reguläre Sprachen
DFAs und ihre Sprachen
17 / 151
Die Sprache L(A) und reguläre Sprachen
Die von einem DFA A = (Σ, Q, δ, q0 , F ) akzeptierte Sprache L(A) ist
L(A) := { w ∈ Σ∗ : δ(q0 , w ) ∈ F }.
Ein Wort w ∈ Σ∗ gehört also genau dann zur Sprache L(A),
wenn w vom DFA A akzeptiert wird.
Eine Sprache L heißt regulär, wenn es einen DFA A gibt mit
L(A) = L.
Wir möchten die Klasse aller regulären Sprachen verstehen.
DFAs und ihre Sprachen
18 / 151
Das Pattern Matching Problem
Sei Σ ein Alphabet und w ∈ Σ∗ ein Wort über Σ.
Lw = {u w v : u, v ∈ Σ∗ }
ist das „Pattern Matching Problem“:
Ist das Pattern v ein Teilwort des Textes T ?
? Ist die Sprache Lw regulär?
? Und wenn ja, was ist die kleinstmögliche Zustandszahl eines DFA Aw mit
L(Aw ) = Lw ?
DFAs und ihre Sprachen
Beispiele
19 / 151
Modulo-Rechnen
m und a seien natürliche Zahlen. Für das Alphabet Σ = { 0, 1, . . . , a − 1 } ist
La,m
=
n
w ∈ Σ∗ :
|w |
X
o
wi a|w |−i ≡ 0 (mod m) .
i=1
eine „Modulo-Sprache“.
? Ist die Modulosprache La,m regulär?
? Und wenn ja, was ist die kleinstmögliche Zustandszahl eines DFA Aa,m mit
L(Aa,m ) = La,m ?
DFAs und ihre Sprachen
Beispiele
20 / 151
Zählen
Definiere die „Sprache L des Zählens“ durch
n
o
L =
an b n : n ∈ N .
? Ist L regulär?
? Und wenn ja, was ist die kleinstmögliche Zustandszahl eines DFA A mit
L(A) = L?
DFAs und ihre Sprachen
Beispiele
21 / 151
Minimierung von DFAs
Minimierung
22 / 151
Minimiere die Zustandszahl
A = (Σ, Q A , δ A , q0A , F A ) und B = (Σ, Q B , δ B , q0B , F B ) seien DFAs.
(a) Wir nennen A und B äquivalent, wenn gilt
L(A) = L(B).
(b) A heißt
minimal,
wenn kein mit A äquivalenter DFA eine kleinere Zustandszahl besitzt.
DAS ZIEL:
Gegeben ist ein DFA A.
Bestimme einen minimalen, mit A äquivalenten DFA.
Minimierung
23 / 151
Zustandsminimierung: Die Idee
Der DFA A = (Σ, Q, δ, q0 , F ) sei gegeben.
Die Idee: Wir sollten doch zwei Zustände p, q ∈ Q zu einem einzigen Zustand
verschmelzen dürfen, wenn p und q „äquivalent“ sind,
also dasselbe Ausgabeverhalten besitzen.
Was bedeutet das?
Die Verschmelzungsrelation ≡A ist eine 2-stellige Relation über der Zustandsmenge Q. Wir sagen, dass Zustände p, q ∈ Q äquivalent bzgl. A sind, (kurz
p ≡A q), wenn für alle Worte w ∈ Σ∗ :
δ(p, w ) ∈ F ⇔ δ(q, w ) ∈ F .
Wir nennen ≡A Verschmelzungsrelation, da wir bzgl. ≡A äquivalente Zustände
in einen Zustand verschmelzen möchten.
Minimierung
24 / 151
Die Verschmelzungsrelation ist eine Äquivalenzrelation
Der DFA A = (Σ, Q, δ, q0 , F ) sei gegeben. Zur Erinnerung:
p ≡A q wenn f.a. Worte w ∈ Σ∗ gilt: δ(p, w ) ∈ F ⇔ δ(q, w ) ∈ F .
(a) Die Verschmelzungsrelation ist
I
I
I
reflexiv, f.a. p ∈ Q: p ≡A p,
symmetrisch, f.a. p, q ∈ Q: wenn p ≡A q, dann q ≡A p und
transitiv, f.a. p, q, r ∈ Q: wenn p ≡A q und q ≡A r , dann p ≡A r .
(b) Die Verschmelzungsrelation ist eine Äquivalenzrelation!
Können wir die Zustände einer Äquivalenzklasse von ≡A zu einem einzigen
Zustand verschmelzen?.
Minimierung
Die Verschmelzungsrelation
25 / 151
Was ist zu tun?
Sei der DFA A = (Σ, Q, δ, q0 , F ) gegeben.
Wir führen die folgenden Schritte durch:
1. Wir bestimmen die Äquivalenzklassen der Verschmelzungsrelation ≡A .
2. Für jede Äquivalenzklasse von ≡A verschmelzen wir alle Zustände der Klasse zu
einem einzigen Zustand und fügen „entsprechende“ Übergänge ein. Den neuen
Automaten nennen wir A0 und bezeichnen ihn als
den Äquivalenzklassenautomaten von A.
Minimierung
Die Verschmelzungsrelation
26 / 151
Die wichtigen Fragen
(a) Wie sollen wir die Zustandsübergänge von A0 definieren, so dass
A und A0 dieselbe Sprache berechnen?
(b) Können wir
I
I
die Verschmelzungsrelation ≡A wie auch den
Äquivalenzklassenautomaten A0 effizient berechnen?
(c) Die Anzahl der Zustände von A0 stimmt mit dem Index von ≡A überein.
I
I
Stimmt der Index mit der minimalen Zustandszahl überein?
Wenn ja, dann ist A0 minimal!
Minimierung
Die Verschmelzungsrelation
27 / 151
Wir bestimmen die Verschmelzungsrelation ≡A
Minimierung
Die Verschmelzungsrelation
28 / 151
Zeugen
(1/2)
Sei (Σ, Q, δ, q0 , F ) ein DFA.
(a) Das Wort w ∈ Σ∗ ist Zeuge für die Inäquivalenz von p und q, wenn
δ(p, w ) ∈ F ∧ δ(q, w ) 6∈ F ∨ δ(p, w ) 6∈ F ∧ δ(q, w ) ∈ F .
Wir sagen auch, dass w die Zustände p und q trennt.
(b) Es ist p 6≡A q genau dann, wenn es einen Zeugen für die Inäquivalenz von p
und q gibt, bzw wenn es ein Wort gibt, das p und q trennt.
Minimierung
Die Verschmelzungsrelation
29 / 151
Zeugen
(2/2)
a
b
a
a1
b1
a
b
bb
ε
a, b
b
b
a2
b2
b
a
a
Finde einen Zeugen für die Inäquivalenz von b1 und bb.
Welcher Zeuge trennt ε und a1 ?
Gibt es Zeugen, die die Zustände a1 und a2 trennen?
Minimierung
Die Verschmelzungsrelation
30 / 151
Wir bestimmen alle Paare nicht-äquivalenter Zustände
1. Markiere alle Paarmengen {p, q} mit p ∈ F und q 6∈ F (als nicht-äquivalent).
I
I
Es ist δ(p, ε) ∈ F und δ(q, ε) 6∈ F .
w = ε ist Zeuge für die Nicht-Äquivalenz von p und q.
2. Wenn die Paarmenge {p, q} bereits markiert wurde und
wenn δ(r , a) = p sowie δ(s, a) = q
für ein a ∈ Σ, dann markiere {r , s}.
I
Da p 6≡A q, gibt es einen Zeugen w mit
δ(p, w ) ∈ F und δ(q, w ) 6∈ F oder δ(p, w ) 6∈ F und δ(q, w ) ∈ F .
I
Das Wort aw trennt r und s.
3. Halte, wenn keine neuen Paarmengen {r , s} markiert werden können.
I
Unser Verfahren behauptet, dass p 6≡A q genau dann gilt,
wenn die Paarmenge {p, q} markiert wurde.
Stimmt die Behauptung: Finden wir alle Paare nicht-äquivalenter Zustände?
Minimierung
Die Verschmelzungsrelation
31 / 151
Unser Verfahren funktioniert!
Sei P die Menge aller Paare {p, q} nicht-äquivalenter Zustände, die aber
von unserem Verfahren nicht gefunden werden. Zeige, dass P leer ist!
Angenommen, P ist nicht-leer.
0. {p, q} ∈ P habe unter allen Paaren in P einen kürzesten Zeugen w .
1. Wenn w = ε, dann ist
I
δ(p, ε) ∈ F und δ(q, ε) 6∈ F oder δ(p, ε) 6∈ F und δ(q, ε) ∈ F ,
I
bzw. p ∈ F und q 6∈ F oder p 6∈ F und q ∈ F .
Aber dann haben wir {p, q} im Schritt 1. markiert.
2. Wenn w = au für den Buchstaben a ∈ Σ, dann ist
I
δ(p, au) ∈ F und δ(q, au) 6∈ F oder δ(p, au) 6∈ F und δ(q, au) ∈ F ,
I bzw.
δ(δ(p, a), u) ∈ F und δ(δ(q, a), u) 6∈ F oder
δ(δ(p, a), u) 6∈ F und δ(δ(q, a), u) ∈ F .
Aber dann ist δ(p, a) 6≡A δ(q, a) mit dem kürzeren Zeugen u:
I
I
Nach Annahme haben wir {δ(p, a), δ(q, a)} z.B. in einer Menge Mi markiert
und werden darauf folgend {p, q} in Mi+1 markieren.
Minimierung
Die Verschmelzungsrelation
32 / 151
Der Automat nach allen Verschmelzungen
Wie sieht der Automat nach dem Verschmelzen aller äquivalenten Zustände aus?
- Für Zustand p ∈ Q bezeichnet
[p]A := q ∈ Q | p ≡A q
die Äquivalenzklasse von p.
- Der Äquivalenzklassenautomat A0 für A besitzt
I
die Zustandsmenge
Q 0 :=
I
I
I
[p]A | p ∈ Q ,
0
den Anfangszustand
q0 :=[q0 ]A , die Menge F 0 := [p]A | p ∈ F der akzeptierenden Zustände und
das Programm δ 0 mit
δ 0 ([p]A , a) := [ δ(p, a) ]A
für alle q ∈ Q, a ∈ Σ.
Minimierung
Die Verschmelzungsrelation
33 / 151
Der Minimierungsalgorithmus
Minimierung
Die Verschmelzungsrelation
34 / 151
Berechnung von ≡A und A0
Eingabe: Ein DFA A = (Q, Σ, δ, q0 , F ).
Schritt 1: Entferne aus A alle überflüssigen Zustände, d.h. alle Zustände,
die nicht von q0 aus erreichbar sind.
Schritt 2: Bestimme alle Paarmengen {p, q} mit p, q ∈ Q und p 6≡A q:
1. Markiere alle Paarmengen in M0 :=
{p, q} : p ∈ F , q ∈ Q \ F
; Setze i := 0
2. Wiederhole
Für alle Paarmengen {p, q} mit p 6= q und für alle x ∈ Σ tue folgendes:
3.
Markiere {p, q}, falls {δ(p, x ), δ(q, x )} ∈ Mi .
4.
5.
Sei Mi+1 die Menge aller hierbei neu markierten Paarmengen.
6.
i := i + 1
7. bis Mi = ∅
8. Ausgabe: M := M0 ∪ · · · ∪ Mi−1 .
Schritt 3: Konstruiere A0 := (Q 0 , Σ, δ 0 , q00 , F 0 ):
Q 0 :=
[q]A : q ∈ Q , wobei [q]A =
q00 := [q0 ]A , F 0 :=
[q]A : q ∈ F
p ∈ Q : {p, q} 6∈ M
δ 0 : Q 0 × Σ → Q 0 mit δ 0 [q]A , x := [δ(q, x )]A für alle q ∈ Q und x ∈ Σ.
Minimierung
Die Verschmelzungsrelation
35 / 151
Ist der Algorithmus korrekt und effizient?
In jeder Iteration in Schritt 2 wird mindestens eine neue Paarmenge markiert:
Es gibt also höchstens |Q|2 Iterationen und der Algorithmus ist effizient (?!).
Die wichtigen Fragen:
1. Sind A und der Äquivalenzklassenautomat A0 äquivalent, d.h. berechnet A0
dieselbe Sprache wie A?
I
I
Zeige, dass die Definition δ 0 ([p], a) := [δ(p, a)]A „wohldefiniert“ ist, also nicht
vom Repräsentanten p abhängt: Wenn p ≡A q, dann ist δ(p, a) ≡A δ(q, a). X
Zeige durch Induktion über die Länge von w , dass
δ 0 ([p], w ) = [δ(p, w )]A
I
sowie
p ≡A q und p ∈ F ⇒ q ∈ F .X
2. Ist A0 minimal?
Aber zuerst entwerfen wir „wirklich-effiziente“ Minimierungsalgorithmen.
Minimierung
Die Verschmelzungsrelation
36 / 151
Die Algorithmen von Moore und Hopcroft
Minimierung
Die Algorithmen von Moore und Hopcroft
37 / 151
Berechnung der Verschmelzungsrelation: Der Ansatz (1/2)
Der Verschmelzungsalgorithmus beginnt mit der Menge M0 aller Paare, die
durch das leere Wort getrennt werden.
Mit vollständiger Induktion: Mi ist die Menge aller Paare mit einem Zeugen
der Länge i.
Sei A = (Σ, Q, δ, q0 , F ) ein DFA. Für jede natürliche Zahl i definiere die
Verschmelzungsrelation ≡iA der Ordnung i:
Setze für alle Zustände p, q ∈ Q
p ≡iA q
:⇐⇒
für alle Worte w ∈ Σ∗ der Länge höchstens i gilt
( δ(p, w ) ∈ F ⇐⇒ δ(q, w ) ∈ F ).
[
Also: p ≡iA q ⇐⇒ {p, q} 6∈
Mj ,
j, j6i
denn Mj ist die Menge aller Paare mit einem Zeugen der Länge j.
Minimierung
Die Algorithmen von Moore und Hopcroft
38 / 151
Berechnung der Verschmelzungsrelation: Der Ansatz (2/2)
Der Verschmelzungsalgorithmus berechnet nacheinander die Äquivalenzklassen
≡0A , ≡1A , . . . , ≡kA ,
wobei ≡kA die Verschmelzungsrelation ist.
Die Äquivalenzrelation ≡0A besitzt die beiden Klassen Q \ F und F .
Betrachte in der iten Iteration alle noch nicht getrennten Zustände p, q.
I
p, q noch nicht getrennt =⇒ Es gilt p ≡i−1
q.
A
I
Gilt δ(p, c) 6≡i−1
δ(q, c) für irgendeinen Buchstaben c, folgt p 6≡iA q.
A
F
Werden δ(p, c) und δ(q, c) von dem Zeugen w getrennt, dann werden p und q
von dem Zeugen cw getrennt.
Minimierung
Die Algorithmen von Moore und Hopcroft
39 / 151
Der Algorithmus von Moore
1. Der DFA A = (Σ, Q, δ, q0 , F ) ist gegeben.
I
I
Z0 = (F , Q \ F ) ist die Zerlegung der Verschmelzungsrelation der Ordnung 0.
Setze i = 0.
2. Wiederhole bis Zi = Zi+1 :
(a) Zi besteht aus den Äquivalenzklassen von ≡iA .
(b) Für alle Buchstaben a ∈ Σ und alle Äquivalenzklassen P von Zi : Bestimme die
Zerlegung Zi (a) der Äquivalenzrelation ≡i,a
A mit
i
i
r ≡i,a
A s :⇐⇒ r ≡A s und δ(r , a) ≡A δ(s, a).
(c) Bestimme die Zerlegung Zi+1 von ≡i+1
als Verfeinerung der Zerlegungen Zi (a).
A
(Beachte
r ≡i+1
s ⇐⇒ r ≡i,a
A
A s für alle a ∈ Σ.)
(d) Setze i = i + 1.
Minimierung
Der Algorithmus von Moore
40 / 151
Der Algorithmus von Moore: Die Laufzeit
Sei A = (Σ, Q, δ, q0 , F ) ein DFA mit n = |Q|. Setze L := L(A).
1. Definiere die Tiefe t von A als die kleinste Zahl i, so dass ≡iA und ≡i+1
A
übereinstimmen.
2. Übungsaufgabe:
I
I
I
I
Die Tiefe stimmt für alle Automaten B mit L(B) = L(A) überein.
Für jede natürliche Zahl n gibt es einen DFA A mit n Zuständen und Tiefe
n − 2. Es gibt keinen DFA mit n Zuständen und Tiefe größer als n − 2.
Die Zerlegung Zi (a) kann in Zeit O(n) bestimmt werden, wenn Zi bekannt ist.
Die Zerlegung Zi+1 kann in Zeit O(|Σ| · n) bestimmt werden, wenn die
Zerlegungen Zi (a) für alle Buchstaben a ∈ Σ bekannt sind.
Moores Algorithmus bestimmt die Verschmelzungsrelation ≡A in Zeit
O(t · |Σ| · n),
wobei t die Tiefe von L = L(A) ist.
Minimierung
Der Algorithmus von Moore
41 / 151
Wie geht Moores Algorithmus vor?
a
b
a
a1
b1
a
b
bb
ε
a, b
b
b
a2
b2
b
a
a
Minimierung
Der Algorithmus von Moore
42 / 151
Hopcrofts Algorithmus: Die Idee
Sei A = (Σ, Q, δ, q0 , F ) ein DFA und seien X , Y ⊆ Q Teilmengen von Q,
wobei keine zwei Zustände y1 ∈ Y und y2 6∈ Y äquivalent seien.
(a) Wir sagen, dass Y die Menge X (für den Buchstaben c) zerlegt, falls es
x1 , x2 ∈ X mit δ(x1 , c) ∈ Y und δ(x2 , c) 6∈ Y gibt.
I
I
δ(x1 , c) und δ(x2 , c) sind nach Annahme nicht äquivalent.
=⇒ x1 und x2 können nicht äquivalent sein.
(b) Setze
δc−1 (Y ) := { q ∈ Q : δ(q, c) ∈ Y }.
(c) Zerlege X in die beiden Klassen
X ∩ δc−1 (Y ) und X \ δc−1 (Y ).
Minimierung
Hopcrofts Algorithmus
43 / 151
Hopcrofts Algorithmus
1. Der DFA A = (Σ, Q, δ, q0 , F ) ist gegeben. Z = (F , Q \ F ) ist die Anfangszerlegung. Setze Check := {Y }, wobei Y die kleinere der Mengen F , Q \ F ist.
/* Während der Berechnung werden die folgenden Invarianten gelten:
(a) Die Äquivalenzklassen der Verschmelzungsrelation ≡A verfeinern Z , d.h. jede
Klasse von Z ist die Vereinigung bestimmter Äquivalenzklassen von ≡A .
(b) Die Klassen X in Z stimmen genau dann mit den Klassen der
Verschmelzungsrelation überein, wenn X ∩ δc−1 (Y ) = X oder X ∩ δc−1 (Y ) = ∅
für alle Klassen X in Z und alle Klassen Y in Check gilt.
F
F
Es gilt X ∩ δc−1 (Q \ F ) = X \ δc−1 (F ) sowie X \ δc−1 (Q \ F ) = X ∩ δc−1 (F ).
Für jedes X ⊆ Q erzeugen Y = F bzw. Y = Q \ F dieselben Kinderklassen.
*/
2. Solange Check nichtleer ist, wiederhole
(a) Wähle irgendeine Klasse Y aus Check und entferne Y aus Check.
(b) Für jeden Buchstaben c ∈ Σ: bestimme δc−1 (Y ) = { q ∈ Q : δ(q, c) ∈ Y } und
alle Klassen X in Z , die von Y zerlegt werden:
F
F
F
Ersetze die „Mutterklasse“ X in Z durch die „Kinderklassen“ X ∩ δc−1 (Y ) und
X \ δc−1 (Y ).
Wenn X ∈ Check, dann ersetze X in Check durch X ∩ δc−1 (Y ) und X \ δc−1 (Y ).
Ansonsten, wenn X 6∈ Check, dann füge die kleinere der beiden Mengen
X ∩ δc−1 (Y ) und X \ δc−1 (Y ) zu Check hinzu.
Minimierung
Hopcrofts Algorithmus
44 / 151
Wie geht Hopcrofts Algorithmus vor?
Der DFA A mit Zustandsdiagramm
1
0
0
0
1
0
1
2
3
1
4
0
5
1
1
0
akzeptiert die Binärdarstellungen aller durch 6 teilbaren Zahlen. D.h.:
L(A) =
n
w ∈ {0, 1}∗ :
|w |
X
o
wi 2|w |−i ≡ 0 (mod 6) .
i=1
Aufgabe: Ist der Automat minimal? Bestimme den Äquivalenzklassenautomaten A0 .
Minimierung
Hopcrofts Algorithmus
45 / 151
Hopcrofts Algorithmus: Korrektheit
Ist die Aktualisierung von Z korrekt?
I
Wird eine Mutterklasse X der Zerlegung Z zerlegt, dann können Zustände in
der einen Kinderklasse X ∩ δc−1 (Y ) nicht mit Zuständen in der anderen
Kinderklasse X \ δc−1 (Y ) äquivalent sein. X
Ist die Aktualisierung der Menge Check korrekt?
I
I
Wird eine Menge Y aus Check entfernt, dann wird Y , nach seiner
Verarbeitung in Schritt 2b), keine Klassen in Z mehr zerlegen. X
Und wenn eine Klasse X durch Y zerlegt wird?
F
F
Gehört X zu Check, dann wird die Mutterklasse X in Check durch beide Kinder
X ∩ δc−1 (Y ), X \ δc−1 (Y ) ersetzt.
Und wenn X nicht zu Check gehört? Warum darf X in Check durch die kleinere
der beiden Kinderklassen ersetzt werden?
Minimierung
Hopcrofts Algorithmus
46 / 151
Hopcrofts Algorithmus: Die Invariante
Wenn X ∈ Z die Klasse X 0 ∈ Z zerlegt, dann gibt es Klassen Y1 , . . . , Y ∈ Check,
die die Zerlegung
0
0
−1
0
−1
X = X ∩ δc (X1 ) ∪ X \ δc (X )}
verfeinern.
X 0 wird also von Y1 , . . . , Yk sukzessive so zerlegt, dass beide Kinderklassen –
mgl. trivial – von X 0 zerlegt werden.
Die Reihenfolge, in der Y1 , . . . , Yk ausgewählt werden, ist beliebig.
Die Invariante wird im zweiten Übungsblatt gezeigt.
Minimierung
Hopcrofts Algorithmus
47 / 151
Hopcrofts Algorithmus: Die Laufzeit
(1/2)
Ein Zustandsübergang δ(q, c) = r gehört genau dann zu einer Klasse Y (der
aktuellen Zerlegung Z ), wenn r ∈ Y .
1. Sei
tc (Y ) := |δc−1 (Y )|
die Anzahl der Übergänge, die zu Y gehören.
P
2. Übungsaufgabe: Y kann in Zeit O( c∈Σ |tc (Y )| ) verarbeitet werden.
3. Wenn die Menge Y mit r ∈ Y aus Check entfernt wird und eine andere Menge
Y 0 mit r ∈ Y 0 irgendwann später zu Check hinzugefügt wird, dann ist
|Y 0 | 6 |Y |/2,
da eine zerlegte Klasse X durch die kleinere der beiden Kinderklassen ersetzt
wird.
I
Zum Zeitpunkt des Hinzufügens von Y 0 gehört die Vorfahrenklasse Y nicht zu
Check, denn r ∈ Y und Y wurde aus Check entfernt.
Minimierung
Hopcrofts Algorithmus
48 / 151
Hopcrofts Algorithmus: Die Laufzeit
(2/2)
(4) Sei C die Menge aller Klassen Y , die irgendwann zur Menge Check gehört
haben. Dann gehört jeder Zustandsübergang zu höchstens log2 n
verschiedenen Mengen Y in Check, und wir erhalten für die Gesamtlaufzeit
X X
X
X X
1
tc (Y ) =
c∈Σ Y ∈C
c∈Σ Y ∈C
=
c∈Σ q∈Q
=
q∈Q : δ(q,c)∈Y
X X
X
Y ∈C : δ(q,c)∈Y
1 =
X
log2 n
(c,q)∈Σ×Q
|Σ| · n · log2 n.
Warum ist Hopcrofts Algorithmus schneller als Moores Algorithmus?
Moore bestimmt nacheinander die vollständigen Zerlegungen ≡iA .
Hopcrofts Algorithmus wird von den einzelnen Klassen Y ∈ Check getrieben
und alle von Y zerlegten Klassen X werden in ihre Kinderklassen aufgeteilt.
Wesentlich: Ein Zustandsübergang gehört zu logarithmisch vielen Klassen.
I
Diese Eigenschaft wird erreicht, weil eine zerlegte Mutterklasse, die nicht zu
Check gehört, nur durch die kleinere Kinderklasse ersetzt werden muss!
Minimierung
Hopcrofts Algorithmus
49 / 151
Die Myhill-Nerode Relation
Minimierung
Die Myhill-Nerode Relation
50 / 151
Was ist Sache?
1. Der ursprüngliche Automat A = (Q, Σ, δ, q0 , F ) und sein
Äquivalenzklassenautomat A0 sind äquivalent.
2. Wir können A0 effizient berechnen.
? Aber hat A0 unter allen mit A äquivalenten DFAs die kleinste Zustandszahl?
Die Myhill-Nerode Relation für die Sprache L = L(A) hat die Antwort.
Minimierung
Die Myhill-Nerode Relation
51 / 151
Die Myhill-Nerode Relation
Sei A = (Σ, Q, δ, q0 , F ) ein DFA. Wenn δ(q0 , u) = δ(q0 , v ), dann gilt
für alle w ∈ Σ∗ : uw ∈ L(A) ⇔ vw ∈ L(A).
L sei eine Sprache über der endlichen Menge Σ, d.h. es gilt L ⊆ Σ∗ .
(a) Die Myhill-Nerode Relation ≡L für L ist eine 2-stellige Relation über Σ∗ .
Für alle Worte u, v ∈ Σ∗ definiere
u ≡L v :⇔ für alle w ∈ Σ∗ gilt: uw ∈ L ⇔ vw ∈ L .
(b) Wir sagen, dass das Wort w ∈ Σ∗ die Worte u, v ∈ Σ∗ trennt,
bzw. dass w ein Zeuge für die Inäquivalenz von u und v ist, wenn
uw ∈ L ∧ vw 6∈ L ∨ uw 6∈ L ∧ vw ∈ L .
(c) Index(L) ist die Anzahl der Äquivalenzklassen von ≡L .
(Entsprechen Äquivalenzklassen von ≡L mgl. Zuständen eines minimalen DFA?)
Minimierung
Die Myhill-Nerode Relation
52 / 151
Die Myhill-Nerode Relation ist eine Äquivalenzrelation
Warum? Die Myhill-Nerode Relation ≡L ist
1. reflexiv, denn u ≡L u gilt f.a. u ∈ Σ∗ ,
2. symmetrisch, denn aus u ≡L v folgt v ≡L u f.a. u, v ∈ Σ∗ ,
3. transitiv, denn aus u ≡L v , v ≡L w folgt u ≡L w f.a. u, v , w ∈ Σ∗ .
Der absolute Hammer:
Für eine reguläre Sprache L stimmt Index(L),
die Anzahl der Äquivalenzklassen von ≡L ,
mit der minimalen Zustandszahl für DFAs A mit L(A) = L überein!
Minimierung
Die Myhill-Nerode Relation
53 / 151
Die minimale Zustandszahl > Index(L)
Der DFA A = (Q, Σ, δ, q0 , F ) akzeptiere die Sprache L, es gelte also L(A) = L.
Angenommen, es ist
δ(q0 , u) = δ(q0 , v ).
1. Dann ist δ(q0 , uw ) = δ(q0 , vw ) für alle Worte w ∈ Σ∗ und A akzeptiert das
Wort uw genau dann, wenn A das Wort vw akzeptiert.
2. Aber L(A) = L und uw ∈ L ⇐⇒ vw ∈ L folgt für alle Worte w ∈ Σ∗ . Also
u ≡L v .
(a) Alle Worte, die auf denselben Zustand von A führen, sind äquivalent bzgl. ≡L .
(b) Jeder DFA A mit L = L(A) hat mindestens Index(L) Zustände.
Minimierung
Die Myhill-Nerode Relation
54 / 151
Ist der Äquivalenzklassenautomat minimal?
Minimierung
Die Myhill-Nerode Relation
55 / 151
Ja, weil:
Der DFA A = (Q, Σ, δ, q0 , F ) akzeptiere die Sprache L, es gelte also L(A) = L.
A0 = (Q 0 , Σ, δ 0 , q00 , F 0 ) sei sein Äquivalenzklassenautomat.
Angenommen, Worte u, v ∈ Σ∗ führen in A0 zu verschiedenen Zuständen.
1. Für A sei p = δ(q0 , u) und q = δ(q0 , v ).
2. Es folgt p 6≡A q und es gibt einen Zeugen w ∈ Σ∗ für die Nicht-Äquivalenz.
I Also:
δ(p, w ) ∈ F ∧ δ(q, w ) 6∈ F ∨ δ(p, w ) 6∈ F ∧ δ(q, w ) ∈ F , bzw.
I
δ(q , uw ) ∈ F ∧ δ(q0 , vw ) 6∈ F ∨ δ(q0 , uw ) 6∈ F ∧ δ(q0 , vw ) ∈ F , bzw.
0
I
uw ∈ L ∧ vw 6∈ L ∨ uw 6∈ L ∧ vw ∈ L .
3. Wenn u und v in A0 zu verschiedenen Zuständen führen, dann folgt u 6≡L v .
Die Zustandszahl von A0 stimmt überein mit Index(L(A)):
Der Äquivalenzklassenautomat A0 ist ein minimaler DFA für L(A).
Minimierung
Die Myhill-Nerode Relation
56 / 151
Einschub: Der Myhill-Nerode Automat
Minimierung
Der Myhill-Nerode Automat
57 / 151
Der Myhill-Nerode Automat NL für L
Können wir einen (sogar minimalen) DFA direkt aus der Myhill-Nerode Relation bauen?
Der Myhill-Nerode Automat NL = (QL , Σ, δL , q0 , FL ) hat die folgenden Komponenten:
die Zustandsmenge
QL :=
[u]L : u ∈ Σ∗ ,
besteht aus den Äquivalenzklassen der Myhill-Nerode Relation ≡L .
Idee: Definiere den Automaten so, dass für alle u ∈ Σ∗ gilt: Der Zustand, in dem
der Automat nach dem Lesen des Worts u ist, gibt die Äquivalenzklasse von u bzgl.
der Myhill-Nerode Relation ≡L an. D.h.:
δL (q0 , u) = [u]L
Startzustand q0 := [ε]L
akzeptierende Zustände FL :=
Programm δL mit
Minimierung
[u]L : u ∈ L
δL [u]L , a := [ua]L für alle u ∈ Σ∗ und a ∈ Σ.
Der Myhill-Nerode Automat
58 / 151
Der Myhill-Nerode Automat ist minimal
(a) Für alle Worte u ∈ Σ∗ gilt δL ([], u) = [u]L und deshalb ist
u ∈ L(NL )
⇐⇒
[u] ∈ FL
⇐⇒
u ∈ L.
(b) NL besitzt genau Index(L) viele Zustände.
NL ist ein minimaler DFA für L.
Minimierung
Der Myhill-Nerode Automat
59 / 151
Der Myhill-Nerode Automat: Beispiele
Bestimme jeweils Index(L) und den Myhill-Nerode Automaten für L.
1. L = {w ∈ {0, 1}∗ : w hat gerade viele Einsen},
2. L die Menge aller Binärdarstellungen für durch 6 teilbare Zahlen,
3. L = {a, b}∗ {ab}{a, b}∗ ,
4. Lu = {w ∈ Σ∗ : u ist ein Teilwort von w } für ein Wort u ∈ Σ∗ .
Minimierung
Der Myhill-Nerode Automat
60 / 151
Welche Sprachen sind nicht regulär?
Der Satz von Myhill-Nerode
Minimierung
Der Myhill-Nerode Automat
61 / 151
Satz von Myhill-Nerode: Wann ist eine Sprache regulär?
Sei Σ ein Alphabet und L ⊆ Σ∗ eine Sprache über Σ.
(a) L ist regulär ⇐⇒ Index(L) ist endlich.
(b) Der minimale DFA für L hat Index(L) Zustände.
Wir haben Teil (b) schon gezeigt. Der Beweis von Teil (a):
=⇒ L ⊆ Σ∗ sei regulär. Dann gibt es einen DFA A mit L = L(A).
I
I
A hat mindestens Index(L) Zustände.
Also ist Index(L) endlich.
⇐= Index(L) sei endlich.
I
I
Der Myhill-Nerode Automat NL ist ein DFA für L, d.h.: L = L(NL ).
L ist regulär.
Minimierung
Der Myhill-Nerode Automat
62 / 151
L = {an b n : n ∈ N} ist nicht regulär
Bestimme unendlich viele Worte uk ∈ {a, b}∗ , so dass
uk 6≡L u`
für alle k 6= ` gilt.
Setze ui := ai . Für k 6= ` gilt uk 6≡L u` , denn
uk b k ∈ L, aber u` b k 6∈ L.
Index(L) = ∞ und L ist nicht regulär.
DFAs können nicht (unbeschränkt) zählen.
Minimierung
Der Myhill-Nerode Automat
63 / 151
L = {ww : w ∈ {a, b}∗ } ist nicht regulär
Wir bestimmen unendlich viele Worte uk ∈ {a, b}∗ , so dass
uk 6≡L u`
für alle k 6= ` gilt.
Setze ui := ai b. Für k 6= ` gilt uk 6≡L u` , denn
uk ak b ∈ L, aber u` ak b 6∈ L.
Index(L) = ∞ und L ist nicht regulär.
DFAs können sich nur beschränkt viele Dinge merken.
Minimierung
Der Myhill-Nerode Automat
64 / 151
Weitere nicht-reguläre Sprachen
Keine der folgenden Sprachen ist regulär.
L1 = { an b m : n, m ∈ N, n 6 m }:
I
DFAs können nicht vergleichen,
L2 = { an b m c n+m : n, m ∈ N }:
I
DFAs können nicht addieren, wenn man sich dazu an die Summanden erinnern
muss,
2
L3 = { an : n ∈ N }:
I
DFAs können nicht quadrieren,
L4 = { w ∈ {a, b}∗ : w ist ein Palindrom }:
I
Endliche Automaten haben ein nur beschränkt großes Gedächtnis.
Minimierung
Der Myhill-Nerode Automat
65 / 151
Das Pumping-Lemma
Das Pumping-Lemma
66 / 151
Vorarbeiten zum Pumping Lemma
(1/2)
Wann ist eine Sprache nicht regulär?
Angenommen, A ist ein Automat mit |Q| Zuständen.
I
Die Zustandsübergänge von A auf einer Eingabe x = x1 · · · xn :
x
x
xn−1
x
x
1
2
3
n
q0 →
q1 →
q2 →
· · · → qn−1 →
qn .
I
I
Wenn n > |Q|, dann werden dabei n+1 > |Q| Zustände durchlaufen.
Es gibt (mind.) einen Zustand q, der (mind.) zweimal durchlaufen wird.
Es gibt Zahlen 0 6 j < k 6 |Q|, so dass
x1 ···xj
q0 → q
Das Pumping-Lemma
xj+1 ···xk
→
q
xk+1 ···xn
→
qn .
67 / 151
Vorarbeiten zum Pumping Lemma
(2/2)
Verarbeitung eines Worts z = z1 · · · zN durch DFA A:
x1 ···xj
Wenn N > |Q|, dann
q0 → q
xj+1 ···xk
→
q
xk+1 ···xN
→
qN .
Und wenn qN ∈ F , dann x ∈ L(A) und
(x1 · · · xj ) · (xk+1 · · · xN ) ∈ L(A)
und
(x1 · · · xj ) · (xj+1 · · · xk ) · (xk+1 · · · xN ) ∈ L(A)
und
(x1 · · · xj ) · (xj+1 · · · xk )2 · (xk+1 · · · xN ) ∈ L(A)
und
3
...
(x1 · · · xj ) · (xj+1 · · · xk ) · (xk+1 · · · xN ) ∈ L(A)
Damit haben wir Folgendes bewiesen:
Das Pumping-Lemma
68 / 151
Das Pumping Lemma
Sei L eine reguläre Sprache.
Dann gibt es eine Pumpingkonstante N > 1, so dass
jedes Wort x ∈ L mit |x | > N
eine Zerlegung mit den folgenden Eigenschaften besitzt:
I
I
x = uvw , |uv | 6 N, |v | > 1,
uv i w ∈ L für jedes i > 0.
und
Fazit: Wenn Worte der Sprache lang genug sind (also |x | > N),
dann gibt es ein nicht-leeres Teilwort v , (also v = xj+1 · · · xk ) das
- „aufgepumpt“ (i > 1)
- und „abgepumpt“ (i = 0) werden kann.
Kennen wir die Pumpingkonstante N?
—NEIN!
Kennen wir die Zerlegung von x in uvw ?
—NEIN! Wir wissen nur, dass |uv | 6 N und |v | > 1 ist.
Das Pumping-Lemma
69 / 151
Anwendung des Pumping Lemmas: Die Spielregeln
Wie kann man das Pumping Lemma nutzen, um zu zeigen, dass eine Sprache L nicht
regulär ist?
(1) Für jede mögliche Pumpingkonstante N > 1
(2) müssen wir ein Wort x ∈ L mit |x | > N konstruieren,
(3) so dass für jede mögliche Zerlegung x = uvw
mit |uv | 6 N und |v | > 1
uv i w 6∈ L
für mindestens ein i > 0 gilt.
Der “Gegner” kontrolliert die Pumpingkonstante N vollständig und die Zerlegung
x = uvw teilweise, denn er muss |uv | 6 N und |v | > 1 garantieren.
Das Pumping-Lemma
70 / 151
Das Pumping Lemma: Ein Anwendungsbeispiel
Die Sprache
L=
n
w ∈ {0, 1}∗ | w = 0n 1m für n 6 m
o
ist nicht regulär.
Beweis: Angenommen, L ist doch regulär.
1
Pumping Lemma: Es gibt eine Pumpingkonstante N > 1, so dass jedes Wort x ∈ L
mit |x | > N eine Zerlegung in x = uvw besitzt, so dass gilt:
(∗) :
|uv | 6 N
und
|v | > 1
und
uv i w ∈ L für alle i > 0.
2
Betrachte insbesondere das Wort x := 0N 1N mit der Zerlegung x = uvw .
3
Es gilt: x ∈ L und |x | > N.
4
Wegen uvw = x = 0N 1N und |uv | 6 N sowie |v | > 1 gibt es eine Zahl k > 1, so
dass v = 0k .
Aber dann ist uv 2 w = 0z+k 1z kein Wort in L, obwohl gemäß Pumping Lemma
dieses Wort in L liegen müsste.
Das Pumping-Lemma
71 / 151
Grenzen des Pumping Lemmas
Es gibt Sprachen, die nicht regulär sind, deren Nicht-Regularität mit dem Pumping
Lemma aber nicht nachgewiesen werden kann.
Die Sprache
L = {a, b}∗ ∪ {c k am b m : k, m > 0}
ist nicht regulär, erfüllt aber die Aussage des Pumping Lemmas. D.h:
Es gibt eine Pumpingkonstante N > 1 (nämlich N = 1), so dass
jedes Wort x ∈ L mit |x | > N
eine Zerlegung mit den folgenden Eigenschaften besitzt:
I
I
x = uvw , |uv | 6 N, |v | > 1,
uv i w ∈ L für jedes i > 0.
und
Beweis: Siehe Tafel!
Das Pumping-Lemma
72 / 151
NFAs
Nichtdeterministische endliche Automaten
73 / 151
NFAs: DFAs, die raten dürfen
Ein „NFA“ akzeptiert ein Eingabewort w ∈ {a, b}∗ genau dann, wenn es im
Automatengraphen mindestens einen Weg gibt,
- der im Startzustand
beginnt,
- dessen Kanten mit w beschriftet sind,
- und der in einem akzeptierenden Zustand
endet.
a
a
a
b
b
Der „NFA“ akzeptiert
L = {w ∈ {a, b}∗ : der vorletzte Buchstabe von w ist ein a }.
Nichtdeterministische endliche Automaten
74 / 151
NFAs: Die formale Definition
Ein nichtdeterministischer endlicher Automat (kurz: NFA)
A = (Σ, Q, δ, q0 , F )
besteht aus:
einer endlichen Menge Σ, dem Eingabealphabet,
einer endlichen Menge Q, der Zustandsmenge,
einer Funktion δ : Q × Σ → P(Q), der Übergangsfunktion,
- die jedem Zustand q ∈ Q und jedem Symbol a ∈ Σ eine Menge
δ(q, a) von möglichen Nachfolgezuständen zuordnet.
- Möglicherweise ist δ(q, a) = ∅: Dann „stürzt“ der Automat ab,
wenn er im Zustand q ist und das Symbol a liest.
dem Startzustand q0 ∈ Q und
einer Menge F ⊆ Q von Endzuständen bzw. akzeptierenden Zuständen.
Nichtdeterministische endliche Automaten
NFAs: Die formale Definition
75 / 151
Der Automatengraph von NFAs
Es sei
- q ∈ Q ein Zustand,
- a ∈ Σ ein Eingabesymbol und
- q 0 ∈ δ(q, a) ein „möglicher Nachfolgezustand“.
Dann gibt es im Automatengraphen einen mit dem Symbol a beschrifteten Pfeil
von Knoten q zu Knoten q 0 , d.h.
q
Nichtdeterministische endliche Automaten
a
q0 .
NFAs: Die formale Definition
76 / 151
Die von einem NFA akzeptierte Sprache
und die erweiterte Übergangsfunktion
Nichtdeterministische endliche Automaten
Die von einem NFA akzeptierte Sprache
77 / 151
Wann akzeptiert ein NFA?
Sei A = (Σ, Q, δ, q0 , F ) ein NFA.
(a) Sei n ∈ N und sei w = a1 · · · an ein Eingabewort der Länge n.
Das Wort w wird ganau dann vom NFA A akzeptiert, wenn es im
Automatengraphen von A einen im Startzustand
q0
beginnenden Weg der Länge n gibt, dessen Kanten mit den Symbolen
a1 . . . an beschriftet sind und der in einem akzeptierenden Zustand endet.
(b) Die von A akzeptierte Sprache L(A) ist
L(A) := {w ∈ Σ∗ : A akzeptiert w }.
Das ist keine „wirklich“ präzise Definition,
denn der Automatengraph soll doch nur unsere Intuition unterstützen.
Nichtdeterministische endliche Automaten
Die von einem NFA akzeptierte Sprache
78 / 151
δ(q, w ) := die MENGE aller möglichen Zustände
nach Lesen von w im „Startzustand“ q
Sei A := (Σ, Q, δ, q0 , F ) ein NFA. Die Funktion
δ : Q × Σ∗ → P(Q)
ist rekursiv wie folgt definiert:
Rekursionsanfang: F.a. q ∈ Q ist δ(q, ε) := {q}.
Rekursionsschritt: F.a. q ∈ Q, w ∈ Σ∗ und a ∈ Σ ist
[
δ(q 0 , a).
δ(q, wa) :=
q 0 ∈δ(q,w )
Ein möglicher Zustand q 00 wird nach Lesen von wa genau dann erreicht, wenn nach
Lesen von w (im Zustand q) ein Zustand q 0 erreicht wird und q 00 ∈ δ(q 0 , a) gilt:
w
a
q → q 0 → q 00 .
Nichtdeterministische endliche Automaten
Die von einem NFA akzeptierte Sprache
79 / 151
Wann genau akzeptiert denn nun ein NFA?
Der NFA A = (Σ, Q, δ, q0 , F ) akzeptiert ein Wort w genau dann, wenn
δ(q0 , w ) ∩ F 6= ∅.
Somit ist
L(A) = { w ∈ Σ∗ : δ(q0 , w ) ∩ F 6= ∅ }.
Nichtdeterministische endliche Automaten
Die von einem NFA akzeptierte Sprache
80 / 151
Äquivalenz von NFAs und DFAs
Äquivalenz von NFAs und DFAs
81 / 151
Akzeptieren NFAs nicht-reguläre Sprachen?
NEIN!
Für jeden NFA A = (Σ, Q, δ, q0 , F ) gibt es einen DFA A0 = (Σ, Q 0 , δ 0 , q00 , F 0 ) mit
L(A0 ) = L(A).
D.h.: NFAs und DFAs akzeptieren genau dieselben Sprachen.
Aber im Allgemeinen sind die DFAs doch bestimmt sehr viel größer?!?
Äquivalenz von NFAs und DFAs
82 / 151
Die Potenzmengenkonstruktion
(1/2)
Sei A = (Σ, Q, δ, q0 , F ) der gegebene NFA.
Idee: Wir konstruieren einen DFA A0 = (Σ, Q 0 , δ 0 , q00 , F 0 ), der in seinem aktuellen
Zustand q 0 ∈ Q 0
die Menge aller Zustände abspeichert, in denen der Automat A in der
aktuellen Situation sein könnte.
Wir definieren die Komponenten von A0 daher wie folgt:
Eingabealphabet Σ,
Zustandsmenge Q 0 := P(Q),
Startzustand q00 := {q0 },
Endzustandsmenge F 0 := {X ∈ Q 0 : X ∩ F 6= ∅ },
Übergangsfunktion δ 0 : Q 0 × Σ → Q 0 , wobei für alle X ∈ Q 0 = P(Q) und alle
a ∈ Σ gilt:
[
δ(q, a).
δ 0 (X , a) :=
q∈X
Äquivalenz von NFAs und DFAs
83 / 151
Die Potenzmengenkonstruktion
(2/2)
Und wie zeigt man, dass A und A0 dieselbe Sprache akzeptieren?
Zeige, dass
δ 0 ({q0 }, w ) = δ(q0 , w )
für jedes Wort w ∈ Σ∗ gilt.
Und wie, bitte schön, sollen wir das zeigen?
Wir haben die erweiterten Übergangsfunktionen δ und δ 0 rekursiv definiert.
Dann sollten wir wohl eine vollständige Induktion nach n = |w | ausführen!
Äquivalenz von NFAs und DFAs
84 / 151
Die Potenzmengenkonstruktion: Ein Beispiel
(1/2)
Wie führt man die Potenzmengenkonstruktion für den NFA
a
a
a
b
b
aus? Bezeichne die Zustände, von links nach rechts gelesen, mit q0 , q1 und q2 .
Wichtig:
1. Beginne mit allen möglichen Nachfolgezuständen des Startzustands
q00 := {q0 }.
2. Definiere die Übergangsfunktion von A0 nur für solche Zustände aus
P({q0 , q1 , q2 }), die vom Startzustand q00 aus erreicht werden können.
Äquivalenz von NFAs und DFAs
85 / 151
Die Potenzmengenkonstruktion: Ein Beispiel
{q0 , q1 , q2 }
(2/2)
a
b
a
{q0 }
a
{q0 , q1 }
b
b
b
a
{q0 , q2 }
Äquivalenz von NFAs und DFAs
86 / 151
NFAs vs. DFAs: Die Zustandszahl
Äquivalenz von NFAs und DFAs
Die Größe von NFAs
87 / 151
Nichtdeterminismus kann Zustände einsparen
Für k ∈ N sei
(1/2)
Lk := {0, 1}∗ · {1} · {0, 1}k−1
Ein NFA, der Lk akzeptiert, kann die Position des k-letzten Buchstabens raten
und dann verifizieren, dass er richtig geraten hat:
0, 1
q0
1
q1
0, 1
q2
0, 1
0, 1
qk
Somit gilt:
Es gibt einen NFA mit k+1 Zuständen, der die Sprache Lk akzeptiert.
Frage: Wie viele Zustände benötigt ein DFA, der Lk akzeptiert?
Antwort: Index(Lk ) — Wie groß ist Index(Lk )?
Äquivalenz von NFAs und DFAs
Die Größe von NFAs
88 / 151
Nichtdeterminismus kann Zustände einsparen
(2/2)
Berechnung von Index(Lk ) für Lk = {0, 1}∗ · {1} · {0, 1}k :
u, v ∈ {0, 1}k seien beliebige, verschiedene Worte der Länge k.
Dann gibt es eine Position i mit ui 6= vi .
Ohne Beschränkung der Allgemeinheit gelte
ui = 0 und vi = 1.
Es ist
v 0i−1
=
v1 · · · vi−1 1 vi+1 · · · vk 0i−1 ∈ Lk ,
aber
u 0i−1
=
/ Lk .
u1 · · · ui−1 0 ui+1 · · · uk 0i−1 ∈
Die Worte u und v sind also nicht Myhill-Nerode äquivalent.
Somit gibt es mindestens 2k paarweise nicht Myhill-Nerode äquivalente Worte und
Index(Lk ) > 2k folgt.
Folgerung: Jeder DFA für Lk hat mindestens 2k Zustände, aber es gibt NFAs für Lk mit
nur k+1 Zuständen.
Äquivalenz von NFAs und DFAs
Die Größe von NFAs
89 / 151
Können auch NFAs effizient minimiert werden?
Wir werden später sehen, dass die Frage
?
L(N) = Σ∗
extrem schwer zu beantworten ist.
Die Frage wäre einfach zu beantworten, wenn wir NFAs effizient minimieren
könnten.
Die Minimierung von NFAs ist knüppelhart.
Äquivalenz von NFAs und DFAs
Die Größe von NFAs
90 / 151
Untere Schranken für die Größe von NFAs
Untere Schranken für NFAs
91 / 151
Vom Index auf untere Schranken für NFAs
Frage:
Wie kann man für eine gegebene Sprache L zeigen, dass jeder NFA, der L erkennt,
mindestens k Zustände hat?
Antwort:
Wenn man Glück hat, gilt Index(L) > 2k , denn dann hat jeder DFA für L mind. 2k
Zustände:
Aus einem NFA für L mit k 0 < k Zuständen könnte man mit der
0
Potenzmengenkonstruktion einen DFA mit 2k < 2k Zuständen bauen.
Wir brauchen bessere Methoden!
Untere Schranken für NFAs
92 / 151
Die Fooling Set Methode
Sei Σ ein endliches Alphabet und L ⊆ Σ∗ eine Sprache über Σ.
Für Worte u1 , . . . , uk , v1 , . . . , vk ∈ Σ∗ heißt die Menge
{ (ui , vi ) : 1 6 i 6 k}
ein Fooling Set für L, falls
(1) für alle i ∈ {1, . . . , k} gilt:
ui vi ∈ L,
(2) für alle i, j ∈ {1, . . . , k} mit i 6= j gilt:
und
ui vj 6∈ L oder uj vi 6∈ L.
Fooling(L) ist die maximale Größe eines Fooling-Sets für L.
Übungsaufgabe:
Jeder NFA für L muss mindestens Fooling(L) Zustände besitzen.
Was ist der Zusammenhang zwischen Index(L) und Fooling(L)?
Wie groß sind NFAs für L = { uv : u, v ∈ {0, 1}k , u 6= v }? Und für
L = { uv : u, v ∈ {0, 1}k , u = v }?
Untere Schranken für NFAs
93 / 151
NFAs mit Epsilon-Übergängen
NFAs mit Epsilon-Übergängen
94 / 151
NFAs mit -Übergängen
Ein NFA mit -Übergängen (kurz: -NFA) ist ein “verallgemeinerter NFA”
(Q, Σ, δ, q0 , F ), dessen Programm eine Funktion der folgenden Form ist:
δ : Q × Σ ∪ {} → P(Q)
Der Automat darf also Zustandsübergänge ausführen, ohne Buchstaben zu lesen.
Frage: Können -NFAs mehr Sprachen akzeptieren als NFAs und DFAs?
Antwort: Nein!
NFAs mit Epsilon-Übergängen
95 / 151
Das Entfernen von -Übergängen: Idee
Entferne -Übergänge nach dem folgenden Schema
5
3
a
a
a
3
1
5
2
a
3
1
b
b
b
6
b
4
4
6
Die Zustandsmenge ist unverändert. Aber die Anzahl der neuen Übergänge kann
quadratisch anwachsen.
NFAs mit Epsilon-Übergängen
96 / 151
Abschlusseigenschaften regulärer Sprachen
Abschlusseigenschaften
97 / 151
Abschlusseigenschaften regulärer Sprachen
(1/6)
L, L1 , L2 ⊆ Σ∗ seien reguläre Sprachen. Dann sind auch die folgenden Sprachen regulär:
(a) L := Σ∗ \ L.
(b) L1 ∪ L2 und L1 ∩ L2 .
(c) L1 · L2 .
(d) L∗ .
Die Klasse aller regulären Sprachen ist also abgeschlossen unter Booleschen Operationen
sowie unter Konkatenation und Stern-Bildung.
Beweis:
(a) Abschluss unter Komplementbildung:
Vertausche akzeptierende und verwerfende Zustände.
Wenn der DFA A = (Q, Σ, δ, q0 , F ) die Sprache L akzeptiert, dann
akzeptiert der Automat B = (Q, Σ, δ, q0 , Q \ F ) die Komplementsprache L.
Abschlusseigenschaften
98 / 151
Abschlusseigenschaften regulärer Sprachen
(2/6)
(b) Abschluss unter Vereinigung:
Verwende -Übergänge.
Wenn die DFAs A1 = (Q1 , Σ, δ1 , q1 , F1 ) und A2 = (Q2 , Σ, δ2 , q2 , F2 ) die Sprachen L1
und L2 akzeptieren, dann akzeptiert der -NFA
A1
3
q0
A2
3
0
A = ({q0 } ∪˙ Q1 ∪˙ Q2 , Σ, δ, q0 , F ∪ F ) die Sprache L1 ∪ L2 .
Abschluss unter Durchschnitt: folgt, da L1 ∩ L2 = L1 ∪ L2 .
Alternative: Verwende den Produktautomaten A = (Q, Σ, δ, q0 , F ) mit
I Q := Q × Q
1
2
I q := (q , q )
0
1
2
I δ (p , p ), a := δ (p , a), δ (p , a) , für alle (p , p ) ∈ Q, a ∈ Σ
1
2
1 1
2 2
1
2
I
für Durchschnitt: F := F1 × F2
für Vereinigung: F := (F1 × Q2 ) ∪ (Q1 × F2 )
Abschlusseigenschaften
99 / 151
Abschlusseigenschaften regulärer Sprachen
(3/6)
Beachte: Reguläre Sprachen sind natürlich nur unter endlicher Vereinigung und
endlicher Durchschnittsbildung abgeschlossen.
Beispiel:
Für jedes n ∈ N besteht die Sprache Ln := {an b n } aus nur einem Wort und ist
damit regulär. Aber
[
Ln
n∈N
ist die Sprache {an b n : n ∈ N}, von der wir wissen, dass sie nicht regulär ist.
Für jedes n ∈ N ist die Sprache L0n := {a, b}∗ \ Ln regulär (da Ln regulär ist und da
die regulären Sprachen unter Komplementbildung abgeschlossen sind).
Aber
\ 0
Ln
n∈N
ist gerade die Sprache {a, b}∗ \ {an b n : n ∈ N}, also das Komplement der Sprache
{an b n : n ∈ N} und daher nicht regulär.
Abschlusseigenschaften
100 / 151
Abschlusseigenschaften regulärer Sprachen
(4/6)
(c) Abschluss unter Konkatenation:
I
I
Verbinde jeden akzeptierenden Zustand von A1 durch einen -Übergang mit
dem Startzustand von A2 .
Die akzeptierenden Zustände von A2 sind die akzeptierenden Zustände des
neuen Automaten.
(d) Abschluss unter Stern-Bildung:
I
I
I
I
Führe einen neuen, akzeptierenden Startzustand q00 ein.
Verbinde alle akzeptierenden Zustände von A durch -Übergänge mit q00 und
verbinde q00 durch einem -Übergang mit dem alten Startzustand q0 .
q00 ist der einzige akzeptierende Zustand des neuen Automaten.
Abschlusseigenschaften
101 / 151
Abschlusseigenschaften regulärer Sprachen
(5/6)
Der Quotient: Seien R, S ⊆ Σ∗ Sprachen. Wenn R regulär ist, dann auch
R/S := { u ∈ Σ∗ : es gibt v ∈ S, so dass uv ∈ R }.
Achtung: Es wird nicht gefordert, dass die Sprache S regulär ist!
Ein Homomorphismus h : Σ∗ → ∆∗ weist jedem Buchstaben a ∈ Σ ein Wort
h(a) ∈ ∆∗ zu. Für ein Wort x = a1 · · · an ∈ Σn ist h(x ) := h(a1 ) · · · h(an ).
Wenn L eine reguläre Sprache ist, dann sind auch
h(L) := { h(x ) : x ∈ L } und h−1 (L) := { x ∈ Σ∗ : h(x ) ∈ L }
regulär.
Eine Substitution ist eine Funktion s : Σ∗ → P(∆∗ ), die jedem Buchstaben a ∈ Σ
eine Sprache s(a) ⊆ ∆∗ zuordnet. Es muss gelten
s() = {} und s(x · y ) = s(x ) · s(y ) für alle x , y ∈ Σ∗ .
Wenn L regulär ist, dann ist auch s(L) regulär.
Abschlusseigenschaften
102 / 151
Abschlusseigenschaften regulärer Sprachen
(6/6)
Wenn L regulär ist, dann auch
Präfix(L) = { u : es gibt v mit uv ∈ L },
1
2L
= { u : es gibt v mit uv ∈ L und |u| = |v |},
Suffix(L)= { v : es gibt u mit uv ∈ L },
Teilwort(L) = { w : es gibt u, v mit uwv ∈ L },
Reverse(L) = { an · · · a2 · a1 : a1 , . . . , an ∈ Σ, a1 · a2 · · · an ∈ L}.
Frage: Und wie zeigt man das?
Antwort: Arbeite mit NFAs.
Abschlusseigenschaften
103 / 151
Entscheidungsprobleme
Entscheidungsprobleme
104 / 151
Welche Fragen sind effizient beantwortbar?
(1/2)
A sei ein DFA oder NFA.
Ist L(A) 6= ∅?
Sei q0 der Anfangszustand von A und sei F die Menge der akzeptierenden Zustände.
L(A) ist genau dann nicht-leer, wenn es einen Weg von q0 zu einem Zustand in F
gibt.
I
I
Wende Tiefensuche auf q0 an.
L(A) ist nicht-leer, wenn Tiefensuche einen akzeptierenden Zustand findet.
Die Laufzeit ist proportional zur Anzahl der Kanten im Zustandsdiagramm, also
proportional zu O(|Σ| · |Q|) für DFAs, bzw. zu O(|Σ| · |Q|2 ) für NFAs.
Entscheidungsprobleme
105 / 151
Welche Fragen sind effizient beantwortbar?
(2/2)
D, D1 , D2 seien deterministische Automaten
Die folgenden Fragen lassen sich effizient beantworten (in Zeit O(|Σ| · |Q|) bzw.
O(|Σ| · |Q1 | · |Q2 |)):
(a) Ist L(D) = Σ∗ ?
(Universalität)
(b) Ist L(D1 ) = L(D2 )?
(Äquivalenz)
(c) Ist L(D1 ) ⊆ L(D2 )?
(“Containment”)
(d) Ist L(D) endlich?
(Endlichkeit)
Beweis: Übungsaufgabe! Idee: Nutze jeweils aus, dass die Frage
Ist L(D) 6= ∅?
effizient beantwortet werden kann.
Die Fragen (a)–(c) sind für NFAs extrem schwierig: Später weisen wir
PSPACE-Vollständigkeit
nach: Diese Fragen sind also mindestens so schwierig wie NP-vollständige Probleme.
Entscheidungsprobleme
106 / 151
Das Wortproblem für NFAs
Für einen NFA A und ein Wort w entscheide, ob A die Eingabe w akzeptiert.
Wie schwierig ist das Wortproblem?
Nicht ganz so einfach wie für DFAs, aber die Menge δ(q0 , w ) der von q0 aus
erreichbaren Zustände lässt sich effizient berechnen: Zeit O(|w | · |Q|2 ) reicht aus!
Algorithmus: Übungsaufgabe!
Akzeptiere genau dann, wenn δ(q0 , w ) ∩ F 6= ∅.
Entscheidungsprobleme
107 / 151
Sehr schwierige Entscheidungsfragen für DFAs und NFAs
(1) Das Interpolationsproblem für DFAs:
Für Teilmengen P, N ⊆ Σ∗ und einen Schwellenwert k > 1,
gibt es einen DFA mit höchstens k Zuständen, der alle Worte in P akzeptiert
und alle Worte in N verwirft?
Dieses Problem ist NP-vollständig. (Hier ohne Beweis)
(2) Das Minimierungsproblem für NFAs:
I
Gegeben zwei NFAs A und B, entscheide, ob B ein zu A äquivalenter NFA mit
minimaler Zustandszahl ist.
Dieses Problem ist PSPACE-vollständig. (Beweis später)
I
Es ist sogar schwierig, die minimale Zustandszahl approximativ zu bestimmen.
I
Was ist da los? Bereits die Frage „L(N) 6= Σ∗ ?“ ist extrem schwer (nämlich
PSPACE-vollständig) und gehört wahrscheinlich nicht einmal zur Klasse NP.
Worte in Σ∗ \ L(N) sind unter Umständen sehr lang.
Entscheidungsprobleme
108 / 151
Reguläre Ausdrücke
Reguläre Ausdrücke
109 / 151
Reguläre „Muster“
Sei Σ ein Alphabet.
1
Die Menge aller Worte über Σ haben wir mit
Σ∗
beschrieben.
2
Sei u ein Wort über Σ. Dann wird die Menge aller Worte über Σ, die u als
Teilwort besitzen, beschrieben durch
Σ∗ · u · Σ∗ .
3
Die Menge aller Worte über Σ, deren vorletzter Buchstabe ein a ist, wird
beschrieben durch:
Σ∗ · a · Σ
Reguläre Ausdrücke
110 / 151
Reguläre Ausdrücke
Die Menge der regulären Ausdrücke über einem endlichen Alphabet Σ wird rekursiv wie
folgt definiert:
Basisregel: Die Ausdrücke ∅, und a für a ∈ Σ sind regulär.
Die Ausdrücke beschreiben die leere Sprache (L(∅) = ∅),
die Sprache des leeren Wortes (L(ε) = {ε}) und
die Sprache des einbuchstabigen Wortes a (L(a) = {a}).
Rekursive Regeln: Sind R und S reguläre Ausdrücke, dann auch
(R | S), (R · S) und R ∗ .
| beschreibt die Vereinigung und wird manchmal auch mit +
bezeichnet (L((R | S)) = L(R) ∪ L(S)),
· die Konkatenation und wird manchmal auch mit ◦ bezeichnet
(L((R · S)) = L(R) · L(S)), und
∗ beschreibt die Kleene-Hülle (L(R ∗ ) = L(R)∗ ).
Reguläre Ausdrücke
111 / 151
Abkürzende Schreibweise
Zur vereinfachten Schreibweise und besseren Lesbarkeit vereinbaren wir folgende
Konventionen:
Den Punkt bei der Konkatenation darf man weglassen.
(Schreibe (RS) statt (R · S))
Bei Ketten gleichartiger Operationen darf man die Klammern weglassen.
(Schreibe (R1 |R2 |R3 ) statt ((R1 |R2 )|R3 ), und (R1 R2 R3 ) statt ((R1 R2 )R3 ))
Äußere Klammern, die einen regulären Ausdruck umschließen, dürfen weggelassen
werden.
Zur besseren Lesbarkeit dürfen zusätzliche Klammern eingefügt werden.
Bei fehlenden Klammern gelten folgende “Präzedenzregeln”:
“∗” bindet stärker als “·”; “·” bindet stärker als “|”.
Beispiel:
a | bbc ∗ ist eine verkürzte Schreibweise für den regulären Ausdruck (a | ((b·b)·c ∗ )).
Die von ihm beschriebene Sprache ist L(a | bbc ∗ ) = {a} ∪ ({bb} · {c}∗ ).
Reguläre Ausdrücke
112 / 151
Reguläre Ausdrücke definieren reguläre Sprachen
Sei Σ ein endliches Alphabet und R ein regulärer Ausdruck über Σ. Dann ist die
Sprache L(R) regulär.
Beweis: Per Induktion über den Aufbau der regulären Ausdrücke.
Induktionsanfang:
Betrachte die gemäß Basisregeln gebildeten regulären Ausdrücke.
∅, , und a, für a ∈ Σ sind reguläre Ausdrücke, die die regulären Sprachen
L(∅) = ∅, L() = {ε} und L(a) = {a} beschreiben.
Induktionsschritt:
Betrachte die gemäß den rekursiven Regeln gebildeten regulären Ausdrücke.
Seien R und S reguläre Ausdrücke, die gemäß Induktionsannahme reguläre
Sprachen L(R) und L(S) beschreiben.
Wir wissen bereits, dass die Klasse der regulären Sprachen abgeschlossen ist
unter Vereinigung, Konkatenation und Kleene-Stern.
=⇒ Auch die folgenden Sprachen sind regulär: L(R) ∪ L(S) = L((R | S)),
L(R) · L(S) = L((R · S)), L(R)∗ = L(R ∗ ).
=⇒ (R | S), (R · S) und R ∗ beschreiben reguläre Sprachen.
Reguläre Ausdrücke
113 / 151
Zwischenstand
Jeder reguläre Ausdruck definiert also eine reguläre Sprache.
Und umgekehrt, gibt es zu jeder regulären Sprache auch einen regulären
Ausdruck?
Reguläre Ausdrücke
114 / 151
Reguläre Sprachen haben reguläre Ausdrücke
(1/3)
Sei Σ ein endliches Alphabet. Zu jeder regulären Sprache L ⊆ Σ∗ gibt es einen regulären
Ausdruck R über Σ mit L = L(R).
Beweis:
Sei A = (Q, Σ, δ, q0 , F ) ein DFA, der L akzeptiert. Es gelte Q = {1, . . . , n}.
k
Idee: Benutze dynamische Programmierung, um reguläre Ausdrücke Rp,q
zu
k
konstruieren, die die Mengen Lp,q beschreiben, wobei
Lkp,q :=
w ∈ Σ∗
:
δ(p, w ) = q, und alle Zwischenzustände
liegen in der Menge {1, . . . , k} ,
für alle p, q ∈ Q und alle k ∈ {0, 1, . . . , n} gilt.
Es ist:
L =
[
Lnq0 ,q .
Für F = {q1 , . . . , qs } wird L daher durch den regulären
q∈F
Ausdruck (Rqn0 ,q1 | · · · | Rqn0 ,qs ) beschrieben.
Reguläre Ausdrücke
115 / 151
Reguläre Sprachen haben reguläre Ausdrücke
(2/3)
Rekursiv (für k ∈ {0, 1, 2, . . . , n}) konstruiere reguläre Ausdrücke Lkp,q für alle p, q ∈ Q.
Reguläre Ausdrücke für L0p,q , für alle p, q ∈ Q:
L0p,q ist die Menge aller Worte, die Zustand q von Zustand p aus
ohne Zwischenzustände erreichen. Also:
I
Falls p 6= q, so ist L0p,q = {a ∈ Σ : δ(p, a) = q}
I
Falls p = q, so ist L0p,q = {ε} ∪ {a ∈ Σ : δ(p, a) = q}
Also ist L0p,q eine endliche Menge von Buchstaben bzw. dem leeren Wort.
0
L0p,q wird von einem regulären Ausdruck Rp,q
beschrieben (durch das Symbol ∅ oder
durch Verknüpfen der Buchstaben bzw. des leeren Wortes mit dem “|”-Operator).
Für alle p, q, r , s ∈ Q und für jedes k > 1 konstruiere reguläre Ausdrücke für die Mengen
Lkp,q , wobei wir annehmen, dass reguläre Ausdrücke für Lk−1
r ,s schon bekannt sind.
Reguläre Ausdrücke
116 / 151
Reguläre Sprachen haben reguläre Ausdrücke
(3/3)
Reguläre Ausdrücke für Lkp,q :
Lkp,q ist die Menge aller Worte w , die Zustand q von Zustand p aus mit
Zwischenzuständen aus der Menge {1, . . . , k} erreichen.
I
Entweder benötigt ein Wort w nur Zwischenzustände in der Menge
{1, . . . , k−1}, d.h. es liegt in Lk−1
p,q ,
I
oder Zustand k ist Zwischenzustand.
F
F
F
I
Dann führt die Berechnung von p nach k,
„pendelt“ zwischen k und k
und erreicht dann q von Zustand k aus.
Wie oft kann Zustand k angenommen werden? Keine Ahnung!
Macht aber nichts, denn
Lkp,q
= Lk−1
∪ Lk−1
Lk−1
p,q
p,k
k,k
∗
Lk−1
k,q .
Daher wird Lkp,q durch den folgenden regulären Ausdruck beschrieben:
k
Rp,q
Reguläre Ausdrücke
k−1
|
:= Rp,q
∗
k−1
k−1
k−1
Rp,k
· Rk,k
· Rk,q
.
117 / 151
Der Satz von Kleene
Wir haben somit den Satz von Kleene bewiesen:
Sei Σ ein endliches Alphabet. Dann gilt
Eine Sprache L ⊆ Σ∗ ist regulär ⇐⇒
Es gibt einen regulären Ausdruck R mit L = L(R).
Fragen:
(a) Wie groß ist der zu einem regulären Ausdruck äquivalente NFA im schlimmsten Fall?
Übung!
(b) Wie groß ist der zu einem regulären Ausdruck äquivalente DFA im schlimmsten Fall?
Übung!
(c) Wie groß ist der zu einem DFA A äquivalente reguläre Ausdruck R im schlimmsten
Fall, wenn wir das obige Verfahren anwenden?
Übung!
Reguläre Ausdrücke
118 / 151
Reguläre Ausdrücke für Komplement und Durchschnitt
(1/2)
Wir wissen: Die Klasse aller regulären Sprachen ist abgeschlossen unter
Komplement- und Durchschnittbildung.
Obwohl die regulären Ausdrücke keine expliziten Operatoren für Komplement- und
Durchschnittbildung enthalten, gibt es daher für alle regulären Ausdrücke R und S
einen regulären Ausdruck
I
R̃, der die Sprache L(R) beschreibt, und
I
T , der die Sprache L(R) ∩ L(S) beschreibt.
Frage: Wie können wir bei gegebenen R und S solche regulären Ausdrücke R̃ und
T konstruieren?
Antwort:
R, S
NFAs
AL(R) , AL(S)
DFAs
BL(R) , BL(S)
DFAs
BL(R) , BL(R)∩L(S)
reguläre Ausdrücke
Laufzeit unserer Verfahren:
Für R̃: 22
O(|R|)
R̃, T .
.
O(|R|+|S|)
Für T : 22
.
Frage: Geht das effizienter?
Reguläre Ausdrücke
119 / 151
Reguläre Ausdrücke für Komplement und Durchschnitt
(2/2)
Wir kennen Verfahren, die bei gegebenen regulären Ausdrücken R und S in Zeit
O(|R|)
I
22
I
22
O(|R|+|S|)
einen regulären Ausdruck R̃ für die Sprache L(R)
einen regulären Ausdruck T für die Sprache L(R) ∩ L(S)
liefern.
Frage: Geht das effizienter?
Antwort von Gelade und Neven (2008):
I
(hier ohne Beweis)
Für R̃ ist unser Verfahren im Wesentlichen optimal:
Es gibt reguläre Ausdrücke Rn der Länge O(n), so dass die kürzesten regulären
n
Ausdrücke, die die Sprache L(Rn ) beschreiben, mindestens die Länge 22 haben.
I
Für T gibt es ein (relativ naheliegendes) Verfahren, das mit Laufzeit 2O(|R|·|S|)
auskommt. Dieses Verfahren ist im Wesentlichen optimal:
Es gibt reguläre Ausdrücke Rn , Sn der Länge O(n2 ), so dass die kürzesten regulären
Ausdrücke für die Sprache L(Rn ) ∩ L(Sn ) mindestens die Länge 2n haben.
Reguläre Ausdrücke
120 / 151
Reguläre Grammatiken
Reguläre Grammatiken
121 / 151
Grammatiken
Programmiersprachen lassen sich am besten als die Sprache aller syntaktisch korrekten
Programme auffassen.
Definiere die Syntax durch eine Grammatik.
Wie erzeugt man arithmetische Ausdrücke mit ganzzahligen Konstanten?
Wir arbeiten mit den Variablen
A: erzeuge einen arithmetischen Ausdruck,
I: erzeuge eine natürliche Zahl und
Z: erzeuge eine Ziffer.
A
→
A + A | A − A | A ∗ A | (A) | I | + I | − I
I
→
ZI |Z
Z
→
0|1|2|3|4|5|6|7|8|9
Wir haben Produktionen (oder Ersetzungsregeln) benutzt.
Reguläre Grammatiken
122 / 151
Die Komponenten einer Grammatik
Eine Grammatik G = (Σ, V , S, P) besteht aus:
einem endlichen Alphabet Σ,
einer endlichen Menge V von Variablen (oder Nichtterminalen) mit Σ ∩ V = ∅,
dem Startsymbol S ∈ V und
einer endlichen Menge P von Produktionen der Form u → v mit
u ∈ (Σ ∪ V )∗ V (Σ ∪ V )∗
und
v ∈ (Σ ∪ V )∗
Beginne mit dem Startsymbol S und wende dann Produktionen an:
Eine Produktion u → v ersetzt ein Vorkommen von u durch ein Vorkommen von v.
Reguläre Grammatiken
123 / 151
Die von einer Grammatik erzeugte Sprache
Für eine Produktion u → v und ein Wort w1 = xuy wird das Wort w2 = xvy
abgeleitet. Wir schreiben
x uy ⇒ x v y .
Für Worte r , s ∈ (Σ ∪ V )∗ schreiben wir
∗
r ⇒s
:⇐⇒
Es gibt Worte w1 = r , w2 , . . . , wk = s, für k > 1, so dass
w1 ⇒ w2 ⇒ · · · ⇒ wk .
s kann in null, einem oder mehreren Schritten aus r abgeleitet werden.
∗
L(G) = w ∈ Σ∗ : S ⇒ w
Reguläre Grammatiken
ist die von der Grammatik G erzeugte Sprache.
124 / 151
Reguläre Grammatiken
Frage: Welcher Typ von Grammatik erzeugt reguläre Sprachen?
Eine Grammatik G = (Σ, V , S, P), bei der alle Produktionen von der Form
X
→
für X ∈ V
X
→
aY
für X , Y ∈ V und a ∈ Σ
oder
sind, heißt (rechts-)regulär.
Die zentralen Fragen:
Wird jede reguläre Sprache von einer regulären Grammatik erzeugt?
Ist die von einer regulären Grammatik erzeugte Sprache regulär?
Reguläre Grammatiken
125 / 151
Reguläre Grammatiken: Ein Beispiel
Eine Grammatik für die Sprache aller Worte über Σ = {a, b}, die das Wort aba als
Teilwort besitzen:
Die Variablen:
S: ist das Startsymbol; es soll ein beliebiges Präfix erzeugen,
Va : bedeutet, dass wir gerade ein a erzeugt haben und dass als nächstes ein b
erzeugt werden soll,
Vab : bedeutet, dass wir gerade ab erzeugt haben und dass als nächstes ein a
erzeugt werden soll,
T : soll ein beliebiges Suffix erzeugen.
Die Produktionen:
Reguläre Grammatiken
S
→
aS | bS | aVa
Va
→
bVab
Vab
→
aT
T
→
aT | bT | 126 / 151
Reguläre Sprachen besitzen reguläre Grammatiken
Sei A = (Q, Σ, δ, q0 , F ) ein NFA, der die Sprache L := L(A) akzeptiert.
Auf Eingabe w = a1 · · · an führt A Zustandsübergänge
a
a
a
1
2
n
q0 →
q1 →
··· →
qn
durch.
Sei G = (Σ, V , S, P) die reguläre Grammatik mit
Variablenmenge V := Q
Startsymbol S := q0
Produktionen
p → aq
für alle p, q, a mit δ(p, a) 3 q
p→
für alle p ∈ F .
Behauptung: Diese Grammatik G erzeugt die Sprache L = L(A).
Reguläre Grammatiken
127 / 151
Reguläre Grammatiken erzeugen reguläre Sprachen
Sei G = (Σ, V , S, P) eine reguläre Grammatik, die die Sprache L := L(G) erzeugt.
Eine Ableitung von G hat die Form
S ⇒ a1 V1 ⇒ a1 a2 V2 ⇒ · · · ⇒ a1 · · · an Vn ⇒ a1 · · · an .
Sei A = (Q, Σ, δ, q0 , F ) der NFA mit
Zustandsmenge Q := V ,
Startzustand q0 := S,
Überführungsfunktion δ : Q × A → P(Q), wobei für alle X ∈ Q und a ∈ Σ gilt:
δ(X , a) := {Y : (X → aY ) ∈ P}.
Endzustandsmenge F := {X ∈ V : (X → ) ∈ P}
Behauptung: Dieser NFA A akzeptiert genau die Sprache L = L(G).
Reguläre Grammatiken
128 / 151
Probabilistische Automaten
Probabilistische Automaten
129 / 151
Würfelnde Automaten
Ein probabilistische endlicher Automat (PFA)
W = (Σ, Q, δ, q0 , F )
darf würfeln: Das Programm
δ : Q × Σ × Q → [0, 1]
weist allen Zuständen p, r ∈ Q und jedem Buchstaben a ∈ Σ die
Wahrscheinlichkeit δ(p, a, r )
zu, dass r als Nachfolgezustand von p gewählt wird, wenn a gelesen wird.
Probabilistische Automaten
130 / 151
Die Übergangsmatrix
Für jeden Buchstaben a ∈ Σ ist Pa die Übergangsmatrix, wobei
Pa [p, r ] := δ(p, a, r )
die Wahrscheinlichkeit ist, dass W von p in r wechselt, wenn a gelesen wird.
Pa ist eine stochastische Matrix:
Für alle Zustände p, r ∈ Q ist Pa [p, r ] > 0 und es ist
Probabilistische Automaten
P
r ∈Q
Pa [p, r ] = 1.
131 / 151
Die erweiterte Übergangsfunktion
Sei W = (Σ, Q, δ, q0 , F ) ein probabilistischer endlicher Automat (PFA).
(a) Für ein Wort u ∈ Σ∗ , einen Anfangszustand p und einen Zustande r ∈ Q ist
δ(p, u, r )
die Wahrscheinlichkeit, dass sich W nach dem Lesen des Wortes u im
Zustand r ∈ Q befindet. Wir geben die folgende rekursive Definition an:
X
δ(p, ua, r ) :=
δ(p, u, s) · δ(s, a, r ).
s∈Q
(b) Die Akzeptanzwahrscheinlichkeit pW (u) des Wortes w wird definiert durch
X
δ(q0 , u, r ).
pW (u) := pr[ W akzeptiert u ] :=
r ∈F
(c) Die reelle Zahl λ ∈ [0, 1] sei gegeben. Die Sprache Lλ (W ) besteht aus allen
Worten u ∈ Σ∗ , die mit Wahrscheinlichkeit größer als λ akzeptiert werden:
Lλ (W ) := { u ∈ Σ∗ : pW (u) > λ}.
Probabilistische Automaten
Die erweiterte Übergangsfunktion
132 / 151
Erweiterte Übergangsfunktion und Matrizenprodukte
Wenn u = a1 · · · an , dann folgt mit vollständiger Induktion:
δ(p, u, r ) = Pa1 · · · Pan [p, r ].
Frage: Ist die Sprache Lλ (W ) für jeden probabilistischen endlichen Automaten
und für jedes λ eine reguläre Sprache?
Probabilistische Automaten
Die erweiterte Übergangsfunktion
133 / 151
Akzeptieren PFAs nur reguläre Sprachen?
Der PFA W = (Σ, Q, δ, q0 , F ) mit
1. Σ = {0, 1},
2. Zustandsmenge Q = {0, 1},
3. Anfangszustand q0 = 0
4. dem akzeptierenden Zustand 1 und
5. dem Programm δ, definiert durch die beiden Übergangsmatrizen
1 1 1 0
P0 = 1 1
und P1 = 2 2 .
0 1
2
2
Für das Wort u = a1 · · · an gilt
PW (u) = Pa1 · · · Pan [0, 1] = 0.an · · · a1 .
Es gibt überabzählbar viele Sprachen Lλ (W ), aber nur abzählbar viele DFAs!
Probabilistische Automaten
Nicht-reguläre Sprachen
134 / 151
Schade?!
Es gibt einen PFA W und einen Schwellenwert λ, so dass Lλ (W ) nicht regulär ist.
Ist Mutter Natur zu tadeln?
Wie sollen wir
?
u ∈ Lλ (W )
experimentell entscheiden, wenn wir nur wenige Berechnungen von W auf u
beobachten dürfen?
Wir sollten für eine reelle Zahl δ > 0 fordern, dass alle Akzeptanzwahrscheinlichkeiten außerhalb eines Intervalls ( λ − δ, λ + δ ) liegen.
Probabilistische Automaten
Nicht-reguläre Sprachen
135 / 151
Akzeptanz mit Lücke
δ sei eine positive reelle Zahl. Ein PFA W akzeptiert die Sprache L = Lλ (W ) mit
(Schwellenwert λ und) Lücke δ, falls
pW (u) 6∈ ( λ − δ, λ + δ )
für alle Worte u ∈ Σ∗ gilt.
Jeder DFA A ist ein PFA, der die Sprache L = L1 (A) mit Schwellenwert 1/2
und der größtmöglichen Lücke 1/2 akzeptiert.
Können PFAs mit großer Lücke Zustände gegenüber DFAs „einsparen“?
I
I
Der Index von EQk = {ww : w ∈ {0, 1}k } beträgt mindestens 2k .
In den Übungen: Es gibt einen PFA mit poly(k) Zuständen, der EQk mit
und Lücke 1−1/k
akzeptiert.
Schwellenwert 1+1/k
2
2
Zeige den Satz von Rabin: Sei W ein PFA, der die Sprache L = Lλ (W ) mit
Lücke δ > 0 akzeptiert. Dann ist die Sprache L regulär.
Probabilistische Automaten
PFAs mit positiver Lücke
136 / 151
Satz von Rabin
(1/2)
W = (Σ, Q, δ, q0 , F ) sei ein PFA.
Angenommen, u1 , . . . , uN sind Vertreter verschiedener Myhill-Nerode Klassen: Für
je zwei Worte ui 6= uj gibt es ein Wort x mit z. B. ui x ∈ L, aber uj x 6∈ L. Also:
pW (ui x )
X
=
δ(q0 , ui , p) · δ(p, x , q) > λ + δ,
p∈Q,q∈F
pW (uj x )
X
=
δ(q0 , uj , p) · δ(p, x , q) 6 λ − δ
p∈Q,q∈F
und insbesondere
2 · δ = λ + δ − (λ − δ) 6
=
pW (ui x ) − pW (uj x )
X δ(q0 , ui , p) − δ(q0 , uj , p) · δ(p, x , q)
p∈Q,q∈F
=
X
(δ(q0 , ui , p) − δ(q0 , uj , p) ·
p∈Q
Probabilistische Automaten
X
δ(p, x , q)
q∈F
Der Satz von Rabin
137 / 151
Satz von Rabin
Wir wissen: 2 · δ 6
(a) 0 6
P
q∈F
(2/2)
P
p∈Q
(δ(q0 , ui , p) − δ(q0 , uj , p) ·
P
q∈F
δ(p, x , q) .
δ(p, x , q) < |Q|, denn 0 6 δ(p, x , q) 6 1 für alle p, q ∈ Q.
(b) Als Konsequenz folgt
2 · δ/|Q| 6
X
|δ(q0 , ui , p) − δ(q0 , uj , p)|.
p∈Q
(c) Die Vektoren
ξi := ( δ(q0 , ui , p) : p ∈ Q )
haben in der 1-Norm also einen Abstand von mindestens 2δ/|Q| voneinander.
(d) Für jedes µ > 0 gibt es aber nur endlich viele Vektoren im |Q|-dimensionalen
Würfel [0, 1]|Q| mit paarweisem Abstand von mindestens µ =⇒
I
I
Der Myhill-Nerode Index von L ist endlich und
L ist regulär.
Probabilistische Automaten
Der Satz von Rabin
138 / 151
Zweiwege Automaten
Zweiwege Automaten
139 / 151
Sprachen, die ohne Speicher akzeptiert werden können
Deterministische Zweiwege Automaten (2DFAs)
- können in jedem Schritt entscheiden, ob sie den vorangegangenen linken oder
den folgenden rechten Buchstaben der Eingabe w ∈ Σ∗ besuchen möchten.
- Das linke Ende der Eingabe ist mit dem Buchstaben α und das rechte Ende mit
dem Buchstaben β beschriftet, wobei α, β 6∈ Σ gelte.
Die formale Definition: Ein 2DFA (Σ, Q, δ, q0 , F ) hat die folgenden Komponenten:
Das Eingabealphabet Σ mit {α, β} ∩ Σ = ∅,
eine endliche Menge Q von Zuständen,
das Programm δ, das wir als Funktion
δ : Q × (Σ ∪ {α, β}) → Q × { links, rechts }
auffassen: Die Eingabe w wird durch das Wort αw β repräsentiert.
Den Anfangszustand q0 ∈ Q
sowie eine Menge F ⊆ Q akzeptierender Zustände.
Zweiwege Automaten
2DFAs
140 / 151
Die Sprache eines Zweiwege Automaten
Sei A ein 2DFA.
1. A beginnt im Zustand q0 und liest den ersten Buchstabens α der Eingabe αw β.
2. δ schreibt Zustandsänderungen, aber auch die Leserichtung vor.
I
I
A darf αw β nicht nach links verlassen.
A akzeptiert das Wort w genau dann, wenn A die transformierte Eingabe αw β
nach rechts in einem Zustand aus F verlässt.
Die Sprache
L(A)
ist die Menge aller von A akzeptierten Worte w ∈ Σ∗ .
Zweiwege Automaten
2DFAs
141 / 151
2DFAs versus DFAs
(a) Können 2DFAs nicht-reguläre Sprachen akzeptieren?
I
Nein, das würde Mutter Natur nicht zulassen.
(b) Gibt es reguläre Sprachen, die 2DFAs mit sehr viel weniger Zuständen
akzeptieren als DFAs? Ja, hier sind einige Beispiele:
I
Lk = {0, 1}∗ · {1} · {0, 1}k−1 ,
I
Mk = {w $w : w ∈ {0, 1}k }.
(c) 2NFAs sind nichtdeterministisch rechnende Zweiwege Automaten.
I
Können 2NFAs nicht-reguläre Sprachen akzeptieren?
Auch das lässt Mutter Natur nicht zu. Aber warum?
I
Gibt es reguläre Sprachen, die 2NFAs mit sehr viel weniger Zuständen
akzeptieren als 2DFAs? Diese Frage ist seit über 50 Jahren offen.
Zweiwege Automaten
2DFAs
142 / 151
2NFAs akzeptieren nur reguläre Sprachen
(1/5)
Wir simulieren den 2NFA N = (Σ, QN , δN , q0 , FN ) durch einen NFA N ∗ .
1. ⊥ ist das Symbol für „undefiniert“ und F ist die Menge aller Funktionen
f : QN → (QN ∪ {⊥}).
2. Die Zustandsmenge von N ∗ ist
QN ∗ = QN × F.
Wenn N ∗ den Zustand (p, f ) annimmt, dann spekuliert N ∗ , dass N eine
Berechnung besitzt, die
(a) den bisher gelesene Präfix der Eingabe zum ersten Mal im Zustand p nach
rechts hin verlässt und
(b) den Präfix im Zustand f (r ) nach rechts verlässt, wenn es den Präfix im Zustand
r von rechts aus betritt. (f (r ) =⊥, wenn N den Präfix nicht mehr verlässt.)
Zweiwege Automaten
2NFAs
143 / 151
2NFAs akzeptieren nur reguläre Sprachen
(2/5)
Fazit: Der Zustand (p, f ) wettet darauf, dass N den bisher gelesenen Präfix
(a) zum ersten Mal nach rechts im Zustand p verlässt wird und
(b) dass f die Reaktion auf einen „Besuch von rechts“ festhält.
3. Zustand p 0 ist für den Buchstaben a konsistent mit (p, f ),
p 0 ∈ K ((p, f ), a),
wenn es eine „mit f konsistente Berechnung“ gibt, die
I
I
im Zustand p „beginnt“ und
zum ersten Mal im Zustand p 0 den „Buchstaben a nach rechts hin verlässt“.
Formal: Es gibt eine Zustandsfolge
(p1 , q1 , . . . , pk−1 , qk−1 , pk ) mit
I
I
p1 = p,
(qi , links) ∈ δN (pi , a) und pi+1 = f (qi ) für i = 1, . . . , k − 1 sowie
(p 0 , rechts) ∈ δN (pk , a).
Zweiwege Automaten
2NFAs
144 / 151
2NFAs akzeptieren nur reguläre Sprachen
(3/5)
Die Funktion f : QN → (QN ∪ {⊥}) sei beliebig.
4. Definition von N ∗ :
I
I
N ∗ darf von seinen Startzustand q0∗ in den Zustand (p, f ) wechseln, falls
(p, rechts) ∈ δN (q0 , α) und (f (r ), rechts) ∈ δN (r , α) für alle r .
Wenn N ∗ den Zustand (p, f ) annimmt: N besitzt eine Berechnung, die α im
Zustand p nach rechts verlässt und f ist die Reaktion dieser Berechnung auf
einen Besuch von α, von rechts kommend. (f (r ) =⊥, wenn δN (α, r ) = ∅.)
N ∗ besitzt einen Zustandsübergang
(p 0 , f 0 ) ∈ δN ∗ (p, f ), a ,
(a) wenn p 0 ∈ K ((p, f ), a) und
(b) für alle Zustände r ∈ QN gibt es eine Berechnung die a von rechts im Zustand r
betritt und später, falls f 0 (r ) 6=⊥, im Zustand f 0 (r ) nach rechts wieder verlässt.
Wie formalisiert man Teil (b)? Es ist (f 0 (r ), rechts ) ∈ δN (r , a) oder es gibt einen
Zustand mit s ∈ QN , so dass (s, links ) ∈ δN (r , a) und f 0 (r ) ∈ K ((s, f ), a).
Zweiwege Automaten
2NFAs
145 / 151
2NFAs akzeptieren nur reguläre Sprachen
(4/5)
Und wenn N eine Eingabeposition mehrmals in demselben Zustand r besucht?
Dann reagiert die Berechnung doch möglicherweise auf „Rechts-Besuche“ im
Zustand r mit verschiedenen Nachfolgezuständen?
O.B.d.A.: Wir können uns auf Berechnungen von N beschränken, die jede
Eingabeposition höchstens einmal im selben Zustand besuchen.
Zweiwege Automaten
2NFAs
146 / 151
2NFAs akzeptieren nur reguläre Sprachen
(5/5)
5. Erfinde einen neuen Zustand „ja“ für N ∗ und setze FN ∗ := { ja }. Wenn N ∗
das Endesymbol β im Zustand (p, f ) liest: Wann sollte N ∗ akzeptieren?
I
Wenn p 0 ∈ K ((p, f ), β) für einen Zustand p 0 ∈ FN gilt.
Definiere in einem solchen Fall
δN ∗ ((p, f ), β) := {( ja , rechts )}.
I
In allen anderen Fällen ist δN ∗ ((p, f ), β) := ∅.
6. Zeige durch vollständige Induktion über die Länge der Eingabe αu:
N ∗ nimmt genau dann den Zustand (p, f ) nach Lesen von αu an, wenn N eine
Berechnung hat, die
F
F
αu zum ersten Mal im Zustand p verlässt
und αu im Zustand f (r ) verlässt, falls αu im Zustand r von rechts betreten
wird.
N akzeptiert w ⇔ N ∗ akzeptiert αw β.
Zweiwege Automaten
2NFAs
147 / 151
2DFAs vs 2NFAs: Die Zustandszahl
(1/2)
Die Sprache
Lk := {0, 1}∗ · {1} · {0, 1}k−1
„trennt“ DFAs und NFAs:
Es gibt einen NFA für Lk mit k + 1 Zuständen,
jeder DFA benötigt mindestens 2k Zustände.
Gibt es eine reguläre Sprache mit kleinen 2NFAs, aber „super-polynomiell“
großen 2DFAs?
(a) Warum ist die Frage interessant?
Dies ist die „einfachste“ Version der Frage, ob „Speicherplatz“ signifikant
eingespart werden kann, wenn nichtdeterministisch gerechnet werden darf.
(b) Warum ist die Frage schwierig?
2DFAs können Teile der Eingabe mehrfach besuchen: Der Myhill-Nerode
Index ist nicht anwendbar.
Zweiwege Automaten
2NFAs
148 / 151
2DFAs vs 2NFAs: Die Zustandszahl
(2/2)
Die Sprache Bk , die möglicherweise 2DFAs und 2NFAs trennt:
(a) Σk sei die Menge aller gerichteten bipartiten Graphen mit den Knotenmengen
L := {links} · {1, . . . , k} und R := {rechts} · {1, . . . , k} sowie der
Kantenmenge E ⊆ L × R.
(b) Für ein Wort w = w1 · · · wn ∈ Σnk identifiziere die Knotenmenge R von wi mit
der Knotenmenge L von wi+1 . Wir erhalten einen n-partiten Graphen G(w ).
I
I
Die Knoten von w1 , die zu L gehören, sind die Quellen von G(w ),
die Knoten von wn , die zu R gehören, sind die Senken von G(w ).
(c) Bk = {w ∈ Σ∗k :
Es gibt einen Weg in G(w ) von einer Quelle zu einer Senke}.
Bk wird von einem NFA mit k Zuständen akzeptiert,
2DFAs „scheinen“ 2Ω(k) Zustände zu benötigen.
Zweiwege Automaten
2NFAs
149 / 151
Zusammenfassung: Reguläre Sprachen
(1/2)
(1) Wir haben deterministische Automaten effizient minimiert.
I
Dazu haben wir den Äquivalenzklassenautomat mit dem
Algorithmus von Moore, bzw. dem Algorithmus von Hopcroft berechnet.
I
Um Minimalität nachzuweisen, haben wir die Myhill-Nerode Relation
definiert =⇒ der Äquivalenzklassenautomat ist minimal.
I
Bis auf eine Umbenennung der Zustände stimmen alle minimalen Automaten
mit dem Myhill-Nerode Automaten überein:
F
Der Index ist eine untere Schranke für die Anzahl benötigter Zustände.
F
Der Satz von Myhill-Nerode: Eine Sprache L ist genau dann regulär, wenn der
Index von L endlich ist.
(2) Mit dem Index oder dem Pumping-Lemma kann man Nicht-Regularität
nachweisen.
Zusammenfassung
150 / 151
Zusammenfassung: Reguläre Sprachen
(2/2)
(3) Nichtdeterministische Automaten erlauben eine kompaktere Beschreibung.
I Die Potenzmengenkonstruktion haben wir für die Bestimmung äquivalenter
deterministischer Automaten benutzt.
I
Mit der Fooling Set Methode haben wir ein Werkzeug zum Nachweis unterer
Schranken für die Größe von NFAs kennengelernt.
(4) DFAs und NFAs akzeptieren genau die Klasse der regulären Sprachen.
I
Reguläre Grammatiken und reguläre Ausdrücke defineren ebenfalls genau
die Klasse der regulären Sprachen.
I
Vernünftige probabilistische endliche Automaten (PFAs mit positiver Lücke),
alternierende Automaten und Zweiwege Automaten, also 2NFAs
akzeptieren genau die Klasse der reguläre Sprachen.
(5) Reguläre Sprachen sind abgeschlossen unter:
I Komplement, Vereinigung, Durchschnitt, Konkatenation, Stern-Bildung,
(inversen) Homorphismen, Substitution und Quotientenbildung.
(6) Viele Entscheidungsfragen können effizient für DFAs beantworted werden. Für
NFAs ist schon die Frage „L(N) 6= Σ∗ ?“ außerst schwierig.
I Aber das Wortproblem „w ∈ L(N)?“ ist effizient lösbar.
Zusammenfassung
151 / 151

Download Report