449
Grammatiken und die Chomsky-Hierarchie [T5.1]
Ziel: Regelsysteme zur Erzeugung von Sprachen.
Beispiel: arithmetische Ausdrücke können definiert werden durch
• a (Variable), a+a, a·a sind arithmet. Ausdr.
• Wenn A und B arithm. Ausdr. sind, dann auch (A)+(B) und (A)·(B).
Grammatik: formalere Beschreibung solcher Regeln.
450
Bestandteile einer Grammatik
• T (oder Σ): endliche Menge von Terminalzeichen (das Alphabet der erzeugten Sprache)
• V : endliche Menge von Variablen (T∩V=∅)• S∈V : Startsymbol• P : endliche Menge von Ableitungsregeln/
ProduktionenPaare (l,r) mit l∈(V∪T )+, r∈(V∪T )*
(Schreibweise: l→r)Variante: l∈V +
451
Beispiel: arithmetische Ausdrücke
V={S}T={(,),a,+,·}P = {S→(S)+(S), S→(S)·(S),
S→a, S→ a+a, S→a·a}
Herleitung eines Wortes:S→ (S)+(S) → (S)+((S)·(S)) → (a·a)+((S)·(S))→ (a·a)+((a)·(S)) → (a·a)+((a)·(a +a))
452
Notation
• w→z⇔ z lässt sich durch Anwendung einer Ableitungsregel (l,r) aus w herleiten,d.h., es gibt in w ein Teilwort l, so dass nach Ersetzen von l durch r das Wort z entsteht.
• w→z⇔ w→w1→w2→w3→…→wn→z, d.h., z kann aus w in endlich vielen Schritten hergeleitet werden.
• L(G): Die von der Grammatik G erzeugte Sprache, also die Menge der Wörter w∈T * mit S→w.*
*
453
Notation
Variablen: Großbuchstaben.Terminale: meistens Kleinbuchstaben a,b,c,...
oder Ziffern, manchmal auch Sonderzeichen oder Klammern.
Wörter aus ( V∪T )*: Kleinbuchstaben u,v, ... oder griechische Kleinbuchstaben.
454
Weiteres BeispielL = { w | w∈{a,b,c}* und w enthält gleich viele
a´s, b´s und c´s }
Angabe einer Grammatik:V = {S,A,B,C,R}, T = {a,b,c},P = {S→R, S→ε,
R→RABC, R→ABCAB →BA, BA →AB, CA →AC, AC →CA, BC →CB, CB →BC, A →a, B →b, C →c}
455
Eingeschränkte Grammatiken
Definition T5.1.1:• Chomsky-0-Grammatiken: Grammatiken
ohne weitere Einschränkungen.• Chomsky-1-Grammatiken: Produktionen
der Form S→ε oder u→v mitu∈V +, v∈((V∪T )– {S})* und |u|�|v|.
(Beispiel: siehe vorherige Folie)
monoton oder kontextsensitiv
456
Eingeschr. Grammatiken (Forts.)
• Chomsky-2-Grammatiken: Produktionen der Form A→v mit A∈V, v∈(V∪T )*.
• Chomsky-3-Grammatiken: Produktionen der Form A→ε oder A→aB mit A,B∈V, a∈T.
kontextfrei
rechtslinear oder regulär
457
Sprachklassen
Li: Menge der von Chomsky-i-Grammatikenerzeugbaren Sprachen, genauer
L0: Chomsky-0-Sprachen (=rekursiv aufzählbare Sprachen)
L1: kontextsensitive Sprachen
L2: kontextfreie Sprachen
L3: rechtslineare Sprachen(=reguläre Sprachen)
458
Chomsky-Hierarchie
Folgerung aus der Definition:L3 ⊂ L2 und L1 ⊂ L0
Später: • L2 ⊂ L1
• Alle Inklusionen sind echt.
459
Chomsky-0-Grammatiken (T5.2)
Ziel: Chomsky-0-Sprachen = rek. aufz. Sprachen
Grammatik: S → Wort*
Turing-Maschine: Wort akz. Konfig.
D.h.: Die Rechnung einer Grammatik verläuft„anders herum“.
460
Rek. Aufz. ⇒ Chomsky-0-Grammatik
Satz T5.2.1: L rekursiv aufzählbar ⇒Es gibt Chomsky-0-Grammatik G mit L(G)=L.
Beweis: Sei L rekursiv aufzählbar und M zugehörige deterministische Turingmaschine, d.h., • x∈L⇒M akzeptiert x,• x∉L⇒M läuft endlos.
461
Vereinfachungen von MM kann modifiziert werden, so dass gilt:• Der Startzustand q0 wird nur zu Beginn der
Rechnung benutzt.• Es gibt nur einen akzept. Zustand q*.• Vor dem Akzeptieren löscht M das Band.Startkonfiguration: q0 w1 … wnAkzep. Konfiguration: q*
462
„Rückwärtsrechnung“ von GV = Q ∪ {S,L,R,X,Y} ∪ (Γ – Σ), Startsymbol S
T = ΣRegeln:1. Erzeugung der Endkonfiguration:
S → Lq*R, q* → q*B, q* → Bq*2. Rückwärtsrechnung:
– δ(q,a)=(q´,a´,1): a´q´ → qa,– δ(q,a)=(q´,a´,–1): q´ba´ → bqa f.a. b∈Γ– δ(q,a)=(q´,a´,0): q´a´ → qa.
EingabealphabetBandalphabet
463
3. Schlussregeln für den Test, ob tatsächlich eine Startkonfiguration beschrieben wird, und zum Löschen der Randmarkierungen:
Bq0 → q0
Lq0 → q0
q0a→ aX f.a. a ∈ΣXa→ aX f.a. a ∈ΣXB → YYB → YYR → εXR → εq0B → Y
Zeichen links des hergel. Wortes löschen
Zum rechten Ende deshergel. Wortes „gehen“
Zeichen rechts des hergel.Wortes löschen
Sonderfall „leeres Wort“
464
Korrektheit
1. L(M)⊆L(G).
Sei c1,…,cm eine akzeptierende Rechnung für w1…wn von M.Dann gibt es in G die HerleitungS � Lq*R� LB…Bq*B…BR = LB…BcmB…BR� LB…Bcm–1B…BR � …� LB…Bc1B…BR = LB…Bq0w1…wnB…BR � w1…wn.
*
*
465
Korrektheit
2. L(G)⊆L(M).
Sei S � Lq*R � w1…wn Herleitung in G.
• L,R, Zustandssymbol können nur mit den Schlussregeln entfernt werden ⇒ LB…Bq0w1…wnB…BR wurde erreicht.
• Die Herleitung Lq*R � LB…Bq0w1…wnB…BR entspricht einer umgekehrten Rechnung von M. ⇒M akzeptiert w1…wn.
*
*
466
Beispiel
Rechnung von M auf „ ab“:q0ab→ cq1b→ cdq2B → cq3dB → q4cBB →q*BBB
Herleitung in G:S → Lq*R → Lq*BR → Lq*BBR → Lq*BBBR→ Lq4cBBR → Lcq3dBR → Lcdq2BR→ Lcq1bBR → Lq0abBR → q0abBR → aXbBR → abXBR → abYR → ab
467
Chomsky-0-Grammatik ⇒ Rek. Aufz.
Satz T5.2.2: Wenn L durch eine Chomsky-0-Grammatik G beschrieben wird, gibt es eine NTM M, die L akzeptiert.
Beweis: Algo von M:
• Schreibe S auf freie Spur.• Iteriere:
– Führe nichtdeterministisch gewählte Ableitungsregel aus
– Vergleiche hergeleitetes Wort mit Eingabe, akzeptiere bei Gleichheit.
468
Umformung NTM �DTM
Satz T5.2.3: Wenn L durch eine NTM Makzeptiert wird, ist L rekursiv aufzählbar.
Beweis: Konstruktion einer DTM für L:For i:=0 to ∞
Sim. alle Rechenwege von M der Länge i. Falls akzeptierende Konfiguration erreicht wird, akzeptiere.
469
Charakterisierung rek. aufz. Spr.
Folgerung T5.2.4:Die Menge der rekursiv aufzählbaren
Sprachen ist gleich1. der Menge der von DTMs akzeptierten
Sprachen,2. der Menge der von NTMs akzeptierten
Sprachen,3. der Menge der von Chomsky-0-
Grammatiken erzeugten Sprachen.
471
DFA � Chomsky-3-Grammatik
Satz T5.3.1:Sei M ein DFA für L. Dann gibt es auch eine
rechtslineare Grammatik G für L.
Beweis:Idee: Rechnung von M mit einer Grammatik
simulieren.V=Q, T=Σ, S=q0,Ableitungsregeln: q� aq´, falls δ(q,a)=q´,
q� ε, falls q∈F.
472
Korrektheit
Rechnung des DFA auf einem Wort w1…wn:
Zustandsfolge q0,q1,…,qn mit δ(qi,wi+1)=qi+1
und qn∈F.
�„Rechnung“ der erzeugten Grammatik:q0 � w1q1 � w1w2q2 � … � w1…wnqn �
w1…wn
q� aq´, falls δ(q,a)=q´,q� ε, falls q∈F.
473
Chomsky-3-Grammatik � NFA
Satz T5.3.1:Sei G eine rechtslineare Grammatik für L.
Dann gibt es auch einen NFA M für L.
Beweis:
Sei rechtslin. Grammatik für L gegeben.
Konstruktion des NFAs:
Q=V, q0=S, F= {A | Regel A�ε vorhanden}
δ(A,a)={B | Regel A� aB vorhanden}
474
Korrektheit
Ableitung von w1…wn hat die FormS�w1A1�w1w2A2�…�w1…wnAn�w1…wn
⇔Mögliche Zustandsfolge des NFAs bei Eingabe w1,…,wn:S� A1 � A2 � … � An
Q=V, q0=S, F= {A | Regel A�ε vorhanden}
δ(A,a)={B | Regel A� aB vorhanden}
475
Charakterisierung d. reg. Sprachen
Folgerung: Die Menge der regulären Sprachen ist gleich
• der Menge der von DFAs oder NFAserkannten Sprachen,
• der Menge der Sprachen, die durch reguläre Ausdrücke beschrieben werden,
• der Menge der Sprachen, die durch Chomsky-3-Grammatiken beschrieben werden.
476
Beobachtung
Grammatiken sind ein auf natürliche Weise nichtdeterministisches Konzept.
Simulationen von Ableitungen einer Grammatik werden mit Hilfe von nichtdeterministischen Maschinen besonders einfach.
477
Kontextfreie Sprachen (Kap. T6)
Überblick:• Beispiele kontextfreier Sprachen• Chomsky-Normalform• Wortproblem für kontextfreie Sprachen• Pumping-Lemma• Mehrdeutigkeit• Algorithmen• Unentscheidbare Probleme• Greibach-Normalform• Maschinenmodell für kontextfreie Sprachen
478
Beispiel: L={0n1n | n≥1}
Haben gesehen: L nicht regulär
(Folien 338 und 346)
Kontextfreie Grammatik:
V={S}, Σ={0,1}, P={S�01, S� 0S1}
� L kontextfrei
479
Variante: L={0i1j | 1�i�j}
Kontextfreie Grammatik:V={S}, Σ={0,1}, P={S�01, S� 0S1, S�S1}
� L kontextfrei
480
Bsp: Sprache der Palindrome
L={w∈{0,1}* | w=wR}
• Haben gesehen: L nicht regulär (Folie 347)• Kontextfreie Grammatik G:
V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}
• Korrektheit:–G erzeugt nur Palindrome.– Alle Palindrome können durch G erzeugt
werden.
L(G)⊆L
L⊆L(G)
481
G erzeugt nur Palindrome.
Behauptung: Alle von G erzeugten Wörter wsind Palindrome.
Induktion über | w|:|w|=0 oder |w|=1: ε, 0, 1 sind Palindrome.
|w|>1: Die erste angewandte Regel ist S�0S0 oder S�1S1, d.h., w beginnt und endet mit demselben Buchstaben. Nach I.V. ist das Wort dazwischen Palindrom ⇒ w Palindrom.
V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}
482
Alle Palindrome w in G herleitbar.
Induktion über | w|:|w|=0 oder |w|=1: ε, 0, 1 sind herleitbar.
|w|>1: w Palindrom ⇒ w beginnt und endet mit 0 (bzw. 1); dazwischen befindet sich ein Palindrom w´, also w=0w´0 oder w=1w´1.
Nach I.V. ist w´ aus S herleitbar.⇒ S � 0S0 � 0w´0 = w bzw.
S � 1S1 � 1w´1 = w.V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}
**
483
Klammersprache
w=w1...wn∈{(,)}* heißt korrekt geklammert, falls
• die Anzahl „(“ ist gleich der Anzahl „)“.• in jedem Anfangsstück w1,...,wi (i�n) ist die
Anzahl „(“ nicht kleiner als die Anzahl „)“.
DefiniereL={w∈{(,)}* | w korrekt geklammert}
Nicht regulär � Folie 349f
Kontextfreie Grammatik: S�SS, S�(S), S�ε.
484
Bsp: L={w| |w|0=|w|1}
|w|0: Anzahl Nullen in w,|w|1: Anzahl Einsen in w.• Übungsaufgabe: Zeige, dass L nicht regulär.• Kontextfreie Grammatik G:
V={S}, Σ={0,1}P={S�ε, S�0S1S, S�1S0S}
• Korrektheit:–G erzeugt nur Wörter aus L.–G erzeugt alle Wörter aus L.
L(G)⊆LL⊆L(G)
485
Beispiel
Ableitung von 110010S�1S0S� 11S0S0S � 1100S� 11001S0S� 110010
P={S�ε, S�0S1S, S�1S0S}
S
1 S 0 S
1 S 0 S 1 S 0 S
ε εε ε
Syntax-baum
486
Korrektheit: L(G)⊆LG erzeugt nur Wörter aus L :
folgt, da bei jedem Ableitungsschritt gleichviele Nullen wie Einsen erzeugt werden.
P={S�ε, S�0S1S, S�1S0S}
487
Korrektheit: L⊆L(G)Induktion über |w|• |w|=0 � w=ε ∈ L(G).• |w|>0, o.B.d.A. beginne w mit 0.
Sei i>0 kleinste Zahl m. |w1…wi|0 = |w1…wi|1. Dann gilt: w1=0, wi=1, |w2…wi–1|0 = |w2…wi–1|1und |wi+1…wn|0=|wi+1…wn|1.
Also w2…wi–1∈ L und wi+1…wn∈ L und
S� 0S1S � 0w2…wi–11wi+1…wn.*
I.V.
488
Syntaxbaum
Graphische Darstellung der Ableitung eines Wortes
• Wurzel: markiert mit S.• Blätter: markiert mit Terminalen/Buchstaben
oder ε.• Innere Knoten:
– markiert mit Variablen A– Nachfolger entsprechen Anwendung einer
Ableitungsregel A�αααα1…ααααr.
489
Anmerkungen
• Zu jeder Ableitung gibt es einen Syntaxbaum.
• Zu einem Syntaxbaum kann es mehrere (äquivalente) Ableitungen geben.
• Linksableitung: Ableitung, bei der die jeweils linkeste Variable ersetzt wird.
• Rechtsableitung: Ableitung, bei der die jeweils rechteste Variable ersetzt wird.
490
Eindeutigkeit und Mehrdeutigkeit
Definition T6.1.5:Eine kontextfreie Grammatik G heißt
eindeutig , wenn es für jedes Wort w∈L(G) nur einen Syntaxbaum gibt.
Eine kontextfreie Sprache heißt eindeutig , wenn es für sie eine eindeutige kontextfreie Grammatik gibt, anderenfalls heißt sie inhärent mehrdeutig .
491
Beispiel: Klammersprache
Die Grammatik S�SS, S�(S), S�ε ist nicht eindeutig. Beispiel: ()()()
Linksableitungen: S�SS�SSS�(S)SS�()SS�()(S)S�()()S�()()(S)�()()()
S�SS�(S)S�()S�()SS�()(S)S�()()S�()()(S)�()()()
Eindeutige Grammatik: S�(S)S, S�ε
492
Weiteres Beispiel
S�ε, S�0S1S, S�1S0S ist mehrdeutig:das Wort 011001 hat die Linksableitungen
S�0S1S�01S0S1S�011S0SS0S1S�011001
undS�0S1S�01S�011S0S�0110S�
01100S1S�011001Etwas schwieriger: Konstruktion einer
eindeutigen Grammatik.
*
*
494
Motivation
• Nahe liegende Vermutung: Syntaxanalyse für eindeutige Grammatiken einfacher.
• Verschiedene Ableitungsbäume haben bei Programmiersprachen häufig verschiedene Semantiken, Beispiel: dangling else.
495
Chomsky-Normalform
Ziel: einfachere Algorithmen für kontextfreie Grammatiken.
Definition T6.2.1: Eine kontextfreie Grammatik ist in Chomsky-Normalform, wenn alle Ableitungsregeln von der FormA� BC oder A� a (mit A,B,C∈V, a∈T)sind.
496
Chomsky-Normalform
Besonderheit: ε kann nicht erzeugt werden.Im Folgenden Umformung
G G´
Kontextfreie Kontextfreie GrammatikGrammatik in Chomsky-Normalform
mit L(G´) = L(G) – {ε}
497
Umformung
Sei s(G) die Größe (Anzahl der Buchstaben in allen Produktionen) der kontextfreien Grammatik G.
Satz T6.2.2: Eine kontextfreie Grammatik Gkann in Zeit O(s(G)2) in Chomsky-Normalform umgeformt werden.
Beweis: Umformung in 4 Schritten
498
Schritt 1: Separation
Ziel: Auf den rechten Seiten der Regeln entweder
• 1 Terminal oder• nur Variablen.Dazu:• erzeuge für jedes a∈T eine neue Variable Ya
und die Regel Ya�a,
• Ersetze auf jeder rechten Seite einer Regel a durch Ya.
499
Beispiel für Schritt 1
A� AbcDeF (mit A,D,F∈V, b,c,e∈T)
wird ersetzt durch
A� AYbYcDYeF, Yb�b, Yc�c, Ye�e
500
Schritt 2: Lange rechte Seiten
A�B1…Bm (mit m≥3, A,B1,…,Bm∈V)
wird ersetzt durch
A� B1C1
C1� B2C2
Ci � Bi+1Ci+1 (für 1�i�m–3)
Cm–2 � Bm–1Bm
Dabei sind C1,…,Cm–2 neue Variablen, die nur für die betrachtete Regel eingeführt werden.
501
Resultat der Schritte 1 und 2
Nur noch Regeln der Form:A� ε (ε-Regeln)A� B (Kettenregeln)A� BC (o.k.)A� a (o.k.)
Bisher: Grammatik hat sich nur um konstanten Faktor vergrößert.
502
Schritt 3: Beseitigung der εεεε-Regeln
1. Teilschritt: Finde alle Var. A mit A�ε.Initialisierung: Variablen A mit Regel A�ε in
Mengen V ´ und Q einfügen.Solange Q≠∅
– Variable B aus Q entnehmen.
– Auf allen rechten Seiten von allen Regeln B durch ε ersetzen.
– Falls neue Regel C�ε entsteht (d.h.C∉V ´): C in V ´ und Q aufnehmen.
Ausgabe: V ´
*
503
Korrektheit des 1. Teilschritts
Behauptung: V ´ enthält genau die Variablen A mit A� ε.
„⊆“ offensichtlich.„⊇“ Induktion über die Länge l der kürzesten
Ableitung A� ε.l=1: Es gibt die Regel A� ε. Dann wird A in V ´ eingefügt.
l>1: Dann A� BC� ε oder A� B � ε.Dann haben B (und C) ε-Ableitungen mit Länge <l und kommen in V ´.
�A wird in V ´ aufgenommen.
*
*
* *
504
Beseitigung der εεεε-Regeln, 2. Teil
• Entferne alle ε-Regeln.• Für jede Regel A�BC:
Falls B∈V ´: erzeuge Regel A�C,falls C∈V ´: erzeuge Regel A�B.
Resultat: Grammatik vergrößert sich nur um konstanten Faktor.
505
Schritt 4: Entf. der Kettenregeln
1. Teilschritt: Äquivalente Variablen entfernen.
• Erzeuge Graphen:Knoten: VariablenKante A�B, falls Kettenregel A�B vorh.
• Suche mit DFS nach KreisenA1 � A2 � A3 � … � Ar � A1
Dann sind A2,…,Ar zu A1 äquivalent und können überall durch A1 ersetzt werden.
506
Schritt 4: Entf. der Kettenregeln
2. Teilschritt: Kettenregeln beseitigen• Ber. Graphen d. Kettenregeln, ist kreisfrei.• Ber. topologische Ordnung A1,…,Ar.• For i:=r downto 1 do
Seien Ai�α1,…,Ai�αs die Regeln mit linker Seite Ai.
Falls Aj�Ai mit j<i vorhanden, lösche Aj�Ai und
erzeuge Aj�α1,…,Aj�αs.
507
Beispiel für den 2. Teilschritt
Graph der Kettenregeln (auf A,B,C,D,E):A D aB E b
RSTopologische Nummerierung berechnenRegeln für E: C�b, C�RS, B�b, B�RSRegeln für D: C�a, (C�b)Regeln für C: A�a, A�b, A�RS, B�a,
B�b, B�RS
C1
2
3 4
5
508
Größenänderung im 4. Schritt
Sei A1,…,Ar die topol. Ordnung der Var.
Im ungünstigen Fall:• Alle Ar-Regeln werden zu A1-,...,Ar–1-
Regeln,• alle Ar–1-Regeln werden zu A1-,...,Ar–2-
Regeln, usw.� Höchstens Quadrierung der Größe.