theorie teil02 4 - fbi = { S } S S 0 | 1 | 00 | 11 S 0S0 | 1S1 ein „längeres“ Beispiel: ein Neger mit Gazelle zagt im Regen nie ... C 01 | 0C1 w = 001100 S A B 0 A 1 B 0 0 1 0

2/4, Folie 1 © 2008 Prof. Steffen Lange - HDa/FbI - Grundlagen der Theoretischen Informatik

Kapitel 2: Formale Sprachen

• Beschreibung für Bezeichner in Programmiersprachen• Beschreibung für „wild cards“ in Skriptsprachen (/* reguläre Ausdrücke */)

• ?; [a-z]; *

• Beschreibung der Syntax von Programmiersprachen• Backus-Naur-Form• erweiterte Backus-Naur-Form

Kontextfreie Sprachen

reguläre Grammatiken/Sprachen

kontextfreie Grammatiken/Sprachen



<Bezeichner> ::= _<Name> | <Name><Name> ::= <Buchstabe> | <Buchstabe><Name'><Name'> ::= <Buchstabe> | <Buchstabe><Name'> | <Ziffer><Name'><Buchstabe>::= a | ... | z | A | ... | Z<Ziffer> ::= 0 | ... | 9


Backus-Naur-Form / erweiterte Backus-Naur-Form (/* Beispiel */)


Kapitel 2: Formale SprachenKontextfreie Sprachen


<Block> ::= <Anweisung> | begin <Anweisung> {<Anweisung>} end<Anweisung> ::= <Zuweisung> | <Verzweigung> | <Schleife><Zuweisung> :: = <Bezeichner> = <Ausdruck><Verzweigung> ::= if <Bedingung> <Block> [else <Block>]<Schleife> := while <Ausdruck> <Block>...

zugehörige kontextfreie Grammatik (/* Beispiel */)

Σ = { begin,end,if,else,while,=,0,...,9 }V = { <Block>,<Anweisung>,<Zuweisung>,...,H1 }S = <Block>




<Block> ::= <Anweisung> | begin <Anweisung> {<Anweisung>} end<Anweisung> ::= <Zuweisung> | <Verzweigung> | <Schleife><Zuweisung> :: = <Bezeichner> = <Ausdruck><Verzweigung> ::= if <Bedingung> <Block> [else <Block>]<Schleife> := while <Ausdruck> <Block>...

zugehörige kontextfreie Grammatik (/* Beispiel */)

<Block> <Anweisung> | begin H1 endH1 <Anweisung> | <Anweisung> H1...<Verzweigung> if <Bedingung> < Block><Verzweigung> if <Bedingung> < Block> else <Block>



konzeptioneller Aspekt

Menge der zulässigen Ausdrücke charakterisieren

• einer Programmiersprache (/* mit Hilfe einer BNF / EBNF */)• ... also auch mit kontextfreien Grammatiken

• einer Seitenbeschreibungssprache / eines Datenaustauschformats(/* mit Hilfe einer Document Type Definition */)• ... also auch mit kontextfreien Grammatiken

algorithmischer Aspekt

das Membership-Problem für eine mittels einer kontextfreien Grammatik Gbeschriebenen Sprache L = L(G) in den Griff bekommen



• ausreichend ausdrucksfähig

• erlauben eine effiziente Lösung des Membership-Problems

... beide Punkte sind im Zusammenhang zu sehen

sind kontextfreie Grammatiken als Beschreibungsmittel


relevante Fragestellungen



...int ggt(int a, int b) {

int teiler = a%b;while (teiler != 0) {

a = b; b = teiler;teiler = a%b;

}return (b);

}

int main ( ) { .. int help = ggt(zaehler,nenner); ...}


Beispiel (/* C++ Funktion */)



...int ggt(int a, int b) {

int teiler = a%b;while (teiler != 0) {

a = b; b = teiler;teiler = a%b;

}return (b);

}

int main ( ) { .. int help = ggt(zaehler,nenner); ...}

solcher Zusammenhänge lassensich mit kontextfreien Grammatikennicht beschreiben

... da hilft man sich auf andere Artund Weise

... für alles andere reichen kontextfreie Grammatiken


Beispiel (/* C++ Funktion */)



kontexfreie Grammatiken/Sprachen

• es sei G = [Σ,V,S,R] eine Chomsky-Grammatik

G heißt kontextfreie Grammatik, falls für alle Regeln l r von G gilt:

• | l | ≤ | r | (/* die Regeln sind nicht verkürzend */)• l ∈ V

Eine Sprache L heißt kontextfreie Sprache, falls es eine kontextfreieGrammatik G mit L(G) = L gibt.




Beispiel

• Sprache L, die alle Zeichenketten enthält, die nur aus 0‘en und 1‘enbestehen und Palindrome sind (/* ergeben von vorn und hinten gelesendieselbe Zeichenkette */)

Σ = { 0,1 }V = { S }S

S 0 | 1 | 00 | 11S 0S0 | 1S1

ein „längeres“ Beispiel: ein Neger mit Gazelle zagt im Regen nie(/* einnegermitgazellezagtimregennie */)



Beispiel

• L = { 0i°1j°0k | i, j, k ≥ 1 und ( i = j oder j = k ) }

Σ = { 0,1 }V = { S,A,B,C }S

S AB | CAA 0 | 0A B 10 | 1B0C 01 | 0C1



zentraler Begriff: Ableitungsbaum

Ein Ableitungsbaum für w ist ein Baum, für den gilt:• seine Wurzel ist mit S markiert• jeder innere Knoten ist mit einer Variablen A ∈ V markiert• die Söhne eines inneren Knotens mit der Variablen A ergeben von

links nach rechts gelesen die rechte Seite einer Regel zumErsetzen von A

• die Blätter sind mit Buchstaben x ∈ Σ markiert(/ *die Blätter – von links nach rechts gelesen – ergeben gerade dieZeichenkette w */)

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik• es sei w ∈ L(G)



Ableitungsbäume (/* Beispiele */)

S AB | CAA 0 | 0A B 10 | 1B0C 01 | 0C1

w = 001100

S

A B

0 1 B 0A

0 1 0

S

AC

00 C 1 A

00 1



Beobachtung (/* Teil 1 */)

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik• es sei w ∈ L(G) und B ein Ableitungsbaum für w

.... in B „finden“ sich mehrere Ableitungen des Wortes w

S

AC

00 C 1 A

00 1

S G CA G 0C1A G 0011AG 00110A G 001100

S G CA G C0A G C00G 0C100 G 001100

S G CA G 0C1A G 0C10AG 0C100 G 001100

...



Beobachtung (/* Teil 2 */)

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik• es sei w ∈ L(G)

• es gibt mehrere Ableitungsbäume für w• in jedem Ableitungsbaum „finden“ sich mehrere Ableitungen von w• in jedem Ableitungsbaum „findet“ sich eine eindeutig festgelegte

Linksableitung von w (/* es wird jeweils die am weitesten linksstehende Variable ersetzt */)

• in jedem Ableitungsbaum „findet“ sich eine eindeutig festgelegteRechtsableitung von w (/* es wird jeweils die am weitesten rechtsstehende Variable ersetzt */)



Membership-Problem für kontextfreie Sprachen

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik• es sei w ∈ Σ*

• um herauszukommen, ob w ∈ L(G) gilt, versucht maneine Links- bzw. Rechtsableitung für w zu konstruierenoder nachzuweisen, daß es keine Links- bzw.Rechtsableitung für w gibt

• Linksableitungen Top-Down-Parser• Rechtsableitungen Bottom-Up-Parser



Chomsky-Normalform für kontextfreie Grammatik

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik

G ist in Chomsky-Normalform, falls für alle Regeln (l,r) ∈ R gilt:

• l ∈ V• r = x mit x ∈ Σ oder r = AB mit A,B ∈ V

Einordnung

Es sei L eine kontextfreie Sprache. Dann gibt es eine GrammatikG = [Σ,V,S,R] in Chomsky-Normalform, so daß L(G) = L gilt.



Vorteile von Grammatiken in Chomsky-Normalform (/* Teil 1 */)

• es sei G = [Σ,V,S,R] eine Grammatik in Chomsky-Normalform• es sei w ∈ L(G) mit | w | = n

Jede Ableitung des Worts w benötigt genau 2n-1 viele Ableitungsschritte.

Hintergrund

... jeder Ableitungsbaum für w ist – mit Ausnahme der letzten Ebene –ein Binärbaum



S ACS ABC SBA 0B 1

Σ = { 0,1 }V = { S,A,B,C }S


S

CA

0 B

1

Beispiel

w = 0011

S

A B

0 1



Vorteile von Grammatiken in Chomsky-Normalform (/* Teil 2 */)

• es sei G = [Σ,V,S,R] eine Grammatik in Chomsky-Normalform• es sei w ∈ Σ* mit w = x1...xn• es sei A ∈ V

Das Wort w ist aus der Variablen ableitbar (/* d.h. A *G w */) gdw.einer der folgenden beiden Fälle eintritt:

Fall 1: n = 1 dann muß R die Regel A x1 enthaltenFall 2: n > 1 dann muß es ein z ∈ { 1,...,n-1 }, Variablen B,C ∈ V

und eine Regel A BC in R geben, so daß gilt:B *G a1...azC *G az+1...an

... kann man benutzen, um unter Verwendung des Paradigmas derdynamischen Programmierung einen effizienten Algorithmus zurLösung des Membership-Problems für L(G) zu konzipieren



Cocke-Younger-Kasami Algorithmus

• es sei G = [Σ,V,S,R] eine Grammatik in Chomsky-Normalform• es sei w ∈ Σ* mit w = x1... xn

verwendete Datenstruktur:

• Tabelle der Größe n × n• Zelle t[i][k] enthält Informationen, die das Teilwort xixi+1... xi+k-1

betreffen (/* d.h. das Teilwort, welches in w an der Position i beginntund aus k Zeichen besteht */)• t[i][k] enthält die Variable A ∈ V, falls A *G xixi+1... xi+k-1 gilt

k = 1 A ∈ t[i][1], falls es eine Regel A xi gibt

k > 1 A ∈ t[i][k], falls die Regel A BC zu R gehört und es einz ∈ { 1,...,k-1 } mit B ∈ t[i][z] und C ∈ t[i+z][k-z] gibt

Berechnungsvorschrift:



3

4

2

1

4321ki


Beispiel

S ACS ABC SBA 0B 1

Σ = { 0,1 }V = { S,A,B,C }S

w = 0011



B3

B4

A2

A1

4321ki


Beispiel (cont.)

S ACS ABC SBA 0B 1

w = 0011

0

0

1

1

Σ = { 0,1 }V = { S,A,B,C }S



--B3

B4

SA2

--A1

4321ki


Beispiel (cont.)

S ACS ABC SBA 0B 1

w = 0011

00

01

11

Σ = { 0,1 }V = { S,A,B,C }S



--B3

B4

CSA2

----A1

4321ki


Beispiel (cont.)

S ACS ABC SBA 0B 1

w = 0011

001

011

Σ = { 0,1 }V = { S,A,B,C }S



--B3

B4

CSA2

S----A1

4321ki


Beispiel (cont.)

S ACS ABC SBA 0B 1

w = 0011

0011

S G AC G 0C G 0SB G 0ABB G 00BB G 001B G 0011

Σ = { 0,1 }V = { S,A,B,C }S



• für i = 1,...,n: bestimme T[i][1]

• für k = 2,...,n:für i = 1,...,n - k + 1:

setze T[i][k] = ∅für z = 1,...,k - 1:

füge ein A ∈ V zu T[i][z] hinzu, falls es B,C ∈ Vmit folgenden Eigenschaften gibt:

- B ∈ T[i][z]- C ∈ T[i+ z][k-z]- die Regel A BC gehört zu R

• falls S ∈ T[1][n], gib „ja“ aus; sonst gib „nein“ aus



• es sei G = [Σ,V,S,R] eine Grammatik in Chomsky-Normalform• es sei w ∈ Σ* mit w = x1... xn



• löst das Membership-Problem für eine kontextfreie Sprache L = L(G),falls die Grammatik G in Chomsky-Normalform ist

• der CYK-Algorithmus benötigt O(n3) viele Schritte, um für ein Wort wder Länge n zu entscheiden, ob w ∈ L(G) oder w ∉ L(G) gilt (/* dieGröße von G ist in der O-Notation „versteckt“ */)

• der CYK- Algorithmus basiert auf dem Paradigma der dynamischenProgrammierung





... der CYK-Algorithmus löst das Membership-Problem für allekontextfreien Sprachen

... bevor man den CYK-Algorithmus anwenden kann, ist einArt „pre-processing“ erforderlich


zurück zu Chomsky-Normalformen

• es sei G = [Σ,V,S,R] eine kontextfreie Grammatik• dann kann man aus G eine Grammatik G°= [Σ°,V°,S°,R°] in Chomsky-

Normalform konstruieren, so daß L(G°) = L(G) gilt

Es sei L eine kontextfreie Sprache. Dann gibt es eine GrammatikG = [Σ,V,S,R] in Chomsky-Normalform, so daß L(G) = L gilt.



Beispiel für die Konstruktion von G° (/* einfacher Fall */)

S 0S 0S1

S 0S H0SH1H0 0H1 1

Σ‘ = { 0,1 }V‘ = { S,H0,H1 }S

S° 0S° H0HH S°H1H0 0H1 1

Σ° = { 0,1 }V° = { S°,H0,H1,H }S°

Σ = { 0,1 }V = { S }S

... falls G nur Regeln hat, deren rechte Seite nicht nur aus einer Variablen bestehen



Beispiel für die Konstruktion von G° (/* komplizierterer Fall */)

S 01S 1AS AA 0S1

S 01S 1AS 0S1A 0S1

Σ = { 0,1 }V = { S,A }S

Σ = { 0,1 }V = { S,A }S

... weiter wie zuvor !!!

... falls G Regeln hat, deren rechte Seite aus einer Variablen bestehen




S AA BA 0 | 00B 1 | 11

S 0 | 00A BA 0 | 00B 1 | 11

Σ = { 0,1 }V = { S,A,B }S

Σ = { 0,1 }V = { S,A,B }S

... so nicht !!!

... man sollte systematisch vorgehen

S 0 | 00A 1 | 11A 0 | 00B 1 | 11

Σ = { 0,1 }V = { S,A,B }S




S AA BA 0 | 00B 1 | 11

H1 H2H2 H3H2 0 | 00H3 1 | 11

Σ‘ = { 0,1 }V‘ = { H1,H2,H3 }H1

Σ = { 0,1 }V = { S,A,B }S

... Variablen durchnumerieren, so daß in Regelnder Form Hi Hj immer i < j gilt... ersetze sukzessive, wobei mit dem größtenIndex i begonnen wird

H1 H2H2 1 | 11H2 0 | 00H3 1 | 11

H1 0 | 00 | 1 | 11H2 1 | 11H2 0 | 00H3 1 | 11




S 01S 0AS AA BB SA CA 0B1C 01A

S AA BB SA C

Σ = { 0,1 }V = { S,A,B,C }S

... Variablen so durchnumerieren, daß in Regelnder Form Hi Hj immer i < j gilt, funktioniertnicht immer (/* Zyklen !!! */)



Beispiel für das „pre-processing“ (/* komplizierterer Fall */)

Zyklen eliminieren !!! (/* d.h. Variablen zusammenfassen */)

Σ = { 0,1 }V = { S,C }S

S 01S 0SS CS 0S1C 01S

Σ = { 0,1 }V = { S,A,B,C }S


S AA BB SA C



Beispiel für das „pre-processing“ (/* komplizierterer Fall */)

Σ = { 0,1 }V = { S,C }S

Σ‘ = { 0,1 }V‘ = { H1,H2 }H1

H1 01H1 0H1H1 H2H1 0H11H2 01H1

H1 01H1 0H1H1 01H1H1 0H11H2 01H1

... weiter wie zuvor !!!

Σ = { 0,1 }V = { S,A,B,C }S

S 01S 0SS CS 0S1C 01S




• falls G Regeln enthält, deren rechten Seite nur aus einer Variablenbestehen, so nimm alle Regeln diesen Typs her und gehe wie folgt vor

Schritt 1 (/* Zyklen finden + eliminieren */):suche Zyklen; falls Zyklus x1 x2; ... ; xn x1gefunden, so ersetze x2,...,xn durch x1

Schritt 2 (/* Regeln umformen */):numeriere die Variablen so durch, daß in allen Regelnvom Typ Hi HK stets i < k gilt; ersetze in allen Regelnvom Typ Hi Hk die Variable Hk durch alle rechten Seitender Regeln vom Typ xk r mit |r| > 1 (/* beginne dabei mitdem größten i */)

Kontexfreie Sprachen

Beispiel für die Konstruktion von G° (/* allgemein */)

• anschließend gibt es nur noch Regelen, deren rechte Seiten aus einem Buch-staben oder aus mehr als einem Zeichen bestehen (/* der einfache Fall */)

Documents

theorie teil02 4 - fbi = { S } S S 0 | 1 | 00 | 11 S 0S0 | 1S1 ein „längeres“ Beispiel: ein Neger mit Gazelle zagt im Regen nie ... C 01 | 0C1 w = 001100 S A B 0 A 1 B 0 0 1 0