Grundlagen der Theoretischen Informatik

Grundlagen der Theoretischen Informatik
4. Kellerautomaten und kontextfreie Sprachen (III)
17.06.2015
Viorica Sofronie-Stokkermans
e-mail: [email protected]
1
Übersicht
1. Motivation
2. Terminologie
3. Endliche Automaten und reguläre Sprachen
4. Kellerautomaten und kontextfreie Sprachen
5. Turingmaschinen und rekursiv aufzählbare Sprachen
6. Berechenbarkeit, (Un-)Entscheidbarkeit
7. Komplexitätsklassen P und NP
2
Umformung von Grammatiken
• Startsymbol nur links
Ist das bei einer Grammatik nicht gegeben, kann man es wie folgt erreichen:
– Führe ein neues Startsymbol Sneu ein
– Füge die Regel Sneu → S hinzu.
• Keine nutzlose Symbole
Theorem (cf-Grammatik ohne nutzlose Symbole)
Ist G = (V , T , R, S) eine cf-Grammatik mit L(G ) 6= ∅,
dann existiert eine cf-Grammatik G ′ = (V ′ , T ′ , R ′ , S ′ ) mit:
• G ′ ist äquivalent zu G .
• Jedes x ∈ (V ∪ T ) ist erreichbar und co-erreichbar.
3
Normalform für Regeln
Theorem (Normalform)
Zu jeder Grammatik G (beliebigen Typs) existiert eine äquivalente Grammatik G ′ ,
bei der für alle Regeln P → Q ∈ R ′ gilt:
• Q ∈ V ∗ und P beliebig
• Q ∈ T und P ∈ V
Für alle Typen außer den linearen hat G ′ denselben Typ wie G .
Beweis: Für jedes t ∈ T erzeuge man eine neue Variable Vt .
• V ′ = V ∪ {Vt | t ∈ T }
• R ′ entsteht aus R, indem für jede Regel P → Q ∈ R in Q alle Vorkommen
eines Terminals t durch die zugehörige Variable Vt ersetzt werden. Außerdem
enthält R ′ für jedes t ∈ T eine neue Regel Vt → t.
4
Elimination von ε-Regeln
Idee: Variablen, aus denen ε ableitbar ist, sollten eliminiert werden
5
Elimination von ε-Regeln
Idee: Variablen, aus denen ε ableitbar ist, sollten eliminiert werden
Definition (ε-Regel, nullbare Variablen)
Eine Regel der Form P → ε
(P eine Variable) heißt ε-Regel.
Eine Variable A heißt nullbar, falls A =⇒∗ ε
Theorem (ε-Regeln sind eliminierbar)
Zu jeder cf-Grammatik G existiert eine äquivalente cf-Grammatik G ′
• ohne ε-Regeln und nullbare Variablen,
falls ε 6∈ L(G ),
• mit der einzigen ε-Regel S → ε und der einzigen nullbaren Variablen S,
falls ε ∈ L(G ) und S das Startsymbol ist.
6
Elimination von ε-Regeln
Algorithmus zur Berechnung der nullbaren Variablen
Input: Grammatik G = (V , T , R, S)
Output: nullbare Variablen
S o.B.d.A. in keiner Regel rechts
Alt := ∅
Neu := {A ∈ V | A → ε ∈ R}
while Alt 6= Neu
{ Alt := Neu
für alle (P → Q) ∈ R do
{ if Q = A1 . . . An and Ai ∈ Neu für 1 ≤ i ≤ n and P 6∈ Neu,
then Neu := Neu ∪ {P}
}
}
output Neu
7
Elimination von ε-Regeln
Beweis (Forts.)
Ausgangsgrammatik G habe die Normalform, bei der für jede Regel P → Q:
Q ∈ V ∗ oder Q ∈ T .
Für jede Regel P → A1 . . . An generiere alle möglichen Kombinationen
P → α1 . . . αn
mit
• αi ∈ {ε, Ai }
• α i = Ai
falls Ai nullbar
falls Ai nicht nullbar
Dann
• Füge alle diese neuen Regeln zur Grammatik hinzu
• Entferne alle Regeln der Form A → ε mit A 6= S
8
Elimination von ε-Regeln
Beweis ((Forts.)
Zu zeigen:
Für die neue Grammatik G ′ gilt: L(G ′ ) = L(G )
Vorgehen:
• G hat die Normalform:
Für jede Regel P → Q gilt Q ∈ V ∗ oder Q ∈ T .
• Wir beweisen die etwas stärkere Behauptung
für alle A ∈ V für alle w ∈ (V ∪ T )∗ − {ε}
∗
∗
(A =⇒G w ) gdw (A =⇒ ′ w ) ,
G
• Daraus folgt sofort L(G ′ ) = L(G ).
9
Elimination von ε-Regeln
Beweis (Forts.)
”⇒” letzte Vorlesung.
”⇐” Wir zeigen: Aus A =⇒∗ ′ w folgt A =⇒∗G w (Induktion über Länge
G
einer Ableitung von A nach w in G ′ ):
Induktionsanfang: Länge = 0. Dann ist w = A, und A =⇒∗G A gilt
immer.
Induktionsschritt: Es gelte für alle Ableitungen A =⇒∗ ′ w einer
G
∗
Länge von höchstens n, dass A =⇒G w .
Ist A =⇒∗ ′ w eine Ableitung der Länge n + 1, so gibt es ein ℓ,
G
Wörter w1 , . . . , wℓ und Variablen A1 , . . . , Aℓ mit A =⇒G ′ A1 . . . Aℓ
=⇒∗ ′ w = w1 . . . wℓ . Es gilt jeweils Ai =⇒∗ ′ wi in höchstens n
G
G
Schritten, und wi 6= ε.
10
Elimination von ε-Regeln
Beweis (Forts.)
Nach der Induktionsvoraussetzung folgt daraus:
• für die Originalgrammatik G gibt es Ableitungen Ai =⇒∗G wi
• damit gibt es auch eine Ableitung A1 . . . Aℓ =⇒∗G w .
Da es in G ′ eine Ableitung A =⇒G ′ A1 . . . Aℓ gibt, gibt es in R ′ eine Regel
A → A1 . . . Aℓ . Wie ist diese Regel aus R entstanden?
11
Elimination von ε-Regeln
Beweis (Forts.)
Nach der Induktionsvoraussetzung folgt daraus:
• für die Originalgrammatik G gibt es Ableitungen Ai =⇒∗G wi
• damit gibt es auch eine Ableitung A1 . . . Aℓ =⇒∗G w .
Da es in G ′ eine Ableitung A =⇒G ′ A1 . . . Aℓ gibt, gibt es in R ′ eine Regel
A → A1 . . . Aℓ . Wie ist diese Regel aus R entstanden?
Eine Regel in R ′ entsteht aus einer Regel in R, indem einige nullbare
Variablen gestrichen werden. Es gab also in G nullbare Variablen B1 bis Bm ,
so dass R die Regel
A → A1 . . . Aℓ1 B1 Aℓ1 +1 . . . Aℓ2 B2 . . . Am Bm Am+1 . . . Aℓ
enthält. (m kann auch 0 sein, dann war die Regel selbst schon in R.)
12
Elimination von ε-Regeln
Beweis (Forts.)
Also gilt in G :
A =⇒G A1 . . . Aℓ1 B1 Aℓ1 +1 . . . Aℓ2 B2 . . . Am Bm Am+1 . . . Aℓ
=⇒∗G A1 . . . Aℓ1 Aℓ1 +1 . . . Aℓ2 . . . Am Am+1 . . . Aℓ =⇒∗G w
da ja Bi =⇒∗G ε möglich ist.
✷
13
Elimination von ε-Regeln
Korollar.
L2 ⊆ L1
Das heißt, jede kontextfreie Sprache ist auch kontextsensitiv
14
Elimination von ε-Regeln
Korollar.
L2 ⊆ L1
Das heißt, jede kontextfreie Sprache ist auch kontextsensitiv
Beweis. Regeln einer kontextsensitiven Grammatik müssen folgende Form
haben:
• entweder uAv → uαv
mit u, v , α ∈ (V ∪ T )∗ , |α| ≥ 1, A ∈ V
• oder S → ε
und S kommt in keiner Regelconclusio vor.
Diesen Bedingungen genügt die kontextfreie Grammatik nach Elimination
der ε-Regeln.
15
Elimination von Kettenproduktionen
16
Elimination von Kettenproduktionen
Definition. Eine Regel der Form
A→B
mit A, B ∈ V
heißt Kettenproduktion.
Theorem. (Kettenproduktionen sind eliminierbar)
Zu jeder cf-Grammatik existiert eine äquivalente cf-Grammatik ohne Kettenproduktionen.
17
Elimination von Kettenproduktionen
Beweis.
Sei G = (V , T , R, S) eine kontextfreie Grammatik
ohne ε-Regeln, außer ggf. S → ε.
Konstruiere neue Grammatik wie folgt:
1. Für alle
• Variablenpaare A, B ∈ V ,
• Regeln B → α ∈ R,
A 6= B
mit A =⇒∗ B
α 6∈ V
füge zu R hinzu:
A→α
2. Lösche alle Kettenproduktionen
18
Normalform für cf-Grammatiken
Theorem. Zu jeder cf-Grammatik existiert eine äquivalente cf-Grammatik
• ohne ε-Regeln
(bis auf S → ε, falls ε zur Sprache gehört;
in diesem Fall darf S in keiner Regelconclusio vorkommen),
• ohne nutzlose Symbole,
• ohne Kettenproduktionen,
• so dass für jede Regel P → Q gilt: entweder Q ∈ V ∗ oder Q ∈ T .
19
Normalform für cf-Grammatiken
Beweis.
1. Man teste zunächst, ob S nullbar ist. Falls ja, dann verwende man
Sneu als neues Startsymbol und füge die Regeln Sneu → S | ε zum
Regelsatz hinzu.
2. Man eliminiere nutzlose Symbole.
3. Man eliminiere alle ε-Regeln außer Sneu → ε.
4. Man bringe die Grammatik in die Normalform,
bei der für jede Regel P → Q gilt: entweder Q ∈ V ∗ oder Q ∈ T .
5. Man eliminiere Kettenproduktionen.
6. Zum Schluss eliminiere man noch einmal alle nutzlosen Symbole
(wg. Schritt 3)
20
Normalformen
Unterschied: Grammatiktypen und Normalformen
Gemeinsamkeit: Sowohl Grammatiktypen als auch Normalformen
schränken die Form von Grammatikregeln ein.
Unterschied:
• Grammatiktypen (rechtslinear, kontextfrei usw.)
führen zu unterschiedlichen Sprachklassen
• Normalformen führen zu
den selben Sprachklassen
21
Normalformen
Wozu dann Normalformen?
• Weniger Fallunterscheidungen bei Algorithmen,
die mit Grammatiken arbeiten.
• Struktur von Grammatiken einfacher zu “durchschauen”
22
Normalformen
Wozu dann Normalformen?
• Weniger Fallunterscheidungen bei Algorithmen,
die mit Grammatiken arbeiten.
• Struktur von Grammatiken einfacher zu durchschauen“
”
Zwei Normalformen
Chomsky-Normalform: Baut auf den Umformungen des vorigen Teils auf.
Greibach-Normalform: Ähnlich den rechtslinearen Grammatiken.
23
Chomsky-Normalform
Definition. Eine cf-Grammatik G = (V , T , R, S) ist in ChomskyNormalform (CNF), wenn gilt:
• G hat nur Regeln der Form
A → BC
mit A, B, C ∈ V und
A→a
mit A ∈ V , a ∈ T
(nicht ε!)
• Ist ε ∈ L(G ), so darf G zusätzlich die Regel S → ε enthalten.
In diesem Fall darf S in keiner Regelconclusio vorkommen.
• G enthält keine nutzlosen Symbole.
24
Chomsky-Normalform
Theorem. Zu jeder cf-Grammatik existiert eine äquivalente cf-Grammatik
in Chomsky-Normalform.
25
Chomsky-Normalform
Theorem. Zu jeder cf-Grammatik existiert eine äquivalente cf-Grammatik
in Chomsky-Normalform.
Beweis.
Schritt 1: Wende auf G die Umformungen des letzten Abschnitts an.
Ergebnis:
• G hat keine nutzlosen Symbole
• Alle Regeln haben die Form
1. A → α mit A ∈ V und α ∈ V ∗ , |α| ≥ 2, und
2. A → a mit A ∈ V , a ∈ T
26
Chomsky-Normalform
Beweis (Forts.)
Schritt 2: Regeln so umformen, dass keine Conclusio eine Länge größer 2
hat.
Ersetze jede Regel
A → A1 . . . An mit A, Ai ∈ V , n ≥ 3
durch:
A
→ A1 C1
C1
→ A2 C2
.
..
Cn−2 → An−1 An
Dabei sind die Ci neue Variablen in V .
✷
27
Greibach-Normalform
Definition.
Eine cf-Grammatik G = (V , T , R, S) ist in Greibach-Normalform
(GNF), wenn gilt:
• G hat nur Regeln der Form
A → aα mit A ∈ V und a ∈ T und α ∈ V ∗
• Ist ε ∈ L(G ), so darf G zusätzlich die Regel S → ε enthalten.
In diesem Fall darf S in keiner Regelconclusio vorkommen.
• G enthält keine nutzlosen Symbole.
28
Pumping-Lemma für kontextfreie Sprachen
29
Wiederholung
Theorem (Pumping-Lemma für L3 -Sprachen)
Sei L ∈ RAT.
Dann existiert ein n ∈ N, so dass:
Für alle
x ∈L
mit
|x| ≥ n
existiert eine Zerlegung
x = uv w
u, v , w ∈ Σ
∗
mit
• |v | ≥ 1
• |v | < n
• uv m w ∈ L
für alle m ∈ N
30
Pumping-Lemma für kontextfreie Sprachen
Theorem (Pumping-Lemma für kontextfreie Sprachen)
Sei L kontextfrei.
Dann existiert ein n ∈ N, so dass:
Für alle
z ∈L
mit
|z| ≥ n
existiert eine Zerlegung
z = uv w xy
u, v , w , x, y ∈ Σ
∗
mit
• |vx| ≥ 1
• |vwx| < n
• uv m w x m y ∈ L
für alle m ∈ N
31
Pumping-Lemma für kontextfreie Sprachen
Beweisidee:
Bei der Ableitung eines hinreichend langen Wortes muss es eine Variable
geben, die mehr als einmal auftaucht.
Dies führt zu einer Schleife in der Ableitung, die aufgepumpt werden kann.
32
Pumping-Lemma für kontextfreie Sprachen
Beweisidee:
33
Pumping-Lemma für kontextfreie Sprachen
Anwendung des Pumping-Lemmas für cf-Sprachen
Wenn das cf-Pumping-Lemma für eine Sprache nicht gilt,
dann kann sie nicht kontextfrei sein.
34
Pumping-Lemma für kontextfreie Sprachen
Anwendung des Pumping-Lemmas für cf-Sprachen
Wenn das cf-Pumping-Lemma für eine Sprache nicht gilt,
dann kann sie nicht kontextfrei sein.
Beispiel (Sprachen, die nicht kontextfrei sind)
Für folgende Sprachen kann man mit Hilfe des cf-Pumping-Lemmas zeigen,
dass sie nicht kontextfrei sind:
• {ap | p prim}
• {an b n c n | n ∈ N}
• {zzz | z ∈ {a, b}∗ }.
35
Pumping-Lemma für kontextfreie Sprachen
L1 = {ap | p prim} ist nicht kontextfrei.
Beweis: Wir nehmen an, L1 sei kontextfrei.
Sei dann n die zugehörige Konstante aus dem Pumping-Lemma.
Wir betrachten das Wort z = ap , wobei p prim und p ≥ n + 2.
Es muss dann eine Zerlegung z = uvwxy geben, so dass:
|vx| ≥ 1, |vwx| < n, uv i wx i y ∈ L1 für alle i ≥ 0.
Dann u = ai1 , v = ai2 , w = ai3 , x = ai4 , y = ai5 mit
• i1 + i2 + i3 + i4 + i5 = p
• i2 + i4 ≥ 1,
i2 + i3 + i4 < n
• i1 + mi2 + i3 + mi4 + i5 prim für alle m ≥ 0.
Sei m = i1 + i3 + i5 . Dann kann i1 + mi2 + i3 + mi4 + i5 = (i1 + i3 + i5 )(1 + i2 + i4 )
nicht prim sein, da i1 + i3 + i5 = p − (i2 + i4 ) ≥ p − n ≥ 2 und 1 + i2 + i4 ≥ 2.
Also uv m wx m y 6∈ L1 . Widerspruch.
Also kann L1 nicht kontextfrei sein.
36
Pumping-Lemma für kontextfreie Sprachen
L2 = {am b m c m | m ∈ N} ist nicht kontextfrei
Beweis:
Wir nehmen an, L2 sei kontextfrei.
Sei dann n die zugehörige Konstante aus dem Pumping-Lemma.
Wir betrachten das Wort z = an b n c n .
Es muss dann eine Zerlegung z = uvwxy geben, so dass:
|vx| ≥ 1, |vwx| < n, uv i wx i y ∈ L2 für alle i ≥ 0.
Da |vwx| < n, enthält das Wort vwx höchstens zwei verschiedene
Buchstaben.
Da |vx| ≥ 1, kann uv 2 wx 2 y nicht von allen drei Buchstaben gleich viele
enthalten.
Also kann L2 nicht kontextfrei sein.
37
Pumping-Lemma für kontextfreie Sprachen
L3 = {zzz | z ∈ {a, b}∗ } ist nicht kontextfrei.
Beweis: Wir nehmen an, L3 sei kontextfrei. Sei dann n die zugehörige Konstante aus
dem Pumping-Lemma.
Wir betrachten das Wort z = an ban ban b.
Es muss dann eine Zerlegung z = uvwxy geben, so dass:
|vx| ≥ 1, |vwx| < n, uv i wx i y ∈ L3 für alle i ≥ 0.
Da |vwx| < n, enthält das Wort vwx höchstens ein b.
Fall 1: vwx = ak . Dann wird durch aufpumpen von v , x eine a Sequenz länger als die
anderen, so uv 2 wx 2 y 6∈ L3 .
Fall 2: vwx = ak bam .
Fall 2.1: b kommt nicht in v oder x vor. Dann sind in uv 2 wx 2 y
zwei a Sequenzen länger als die dritte, so uv 2 wx 2 y 6∈ L3 .
Fall 2.2: b kommt in v oder x vor. Dann enthält uv 0 wx 0 y nur zwei
b’s, d.h. uv 0 wx 0 y 6∈ L3 .
Also kann L3 nicht kontextfrei sein.
38

Download Report