URL:         /axel/informatik3_ws9899_blatt10.html
Dieses  Übungsblatt ist alleine zu bearbeiten.
 

Aufgabe 26 (6+6+4 Punkte)
Betrachten Sie das Verfahren von Cocke-Kasami-Younger aus der Vorlesung. Die Grammatik sei bereits in Chomsky-Normalform gegeben.
- entwerfen Sie Datenstrukturen für die schnelle Realisierung des Verfahrens. Geben Sie den
   Algorithmus unter Zuhilfenahme der neuen Datenstrukturen an
- führen Sie ein Beispiel vor, welches den Vorteil der gewählten Datenstruktur zeigt
- schätzen Sie den Zeitaufwand des Verfahrens ab

Aufgabe 27 (6  Punkte)
Betrachten Sie die Sprache L = {aⁱ  b^j  cⁱ  d^j  | i >= 1 und j >= 1}. Beweisen Sie, daß diese Sprache nicht kontext frei ist.  Tip: Pumping Lemma
 

Dies ist eine Korrektur der Aufgabe 22, wo der zweite Exponent falsch war.