URL:         /axel/informatik3_ws0203_blatt8.html
Dieses  Übungsblatt ist in Zweiergruppen zu  bearbeiten.
 

Aufgabe 20 kontextfrei (5 Punkte)
 
Zeigen Sie, dass die Sprache L = { aⁿb²ⁿc³ⁿ | n > 0 }  nicht kontextfrei ist.

Aufgabe 21 Cocke Kasami Younger (3+5 Punkte)

Die Sprache L={a^mb^mcⁿ| m> 1 n>1} ist kontextfrei.  Geben Sie eine Grammatik in Chomsky Normalform an. (3 P) Wählen Sie ein Wort aus der Sprache mit mindestens 8 Zeichen und wenden Sie den CKY Algorithmus an um nachzuweisen, dass es in der Sprache liegt. (5 Punkte)

Aufgabe 22 Variablen (12 Programmierpunkte)
Erweitern Sie die Sprache des Taschenrechners um eine Zuweisung an eine Variable. Dies soll wie in C ein gültiger Ausdruck mit einem Wert sein. Die Priorität der Zuweisung soll wie in C sein. Variablennamen  sind dabei Zeichenketten aus Buchstaben. Wir können annehmen, dass Variablen automatisch mit 0 initialisiert werden. Möglich soll sein:

ein:a=7;
aus: 7
ein: a=a*7.0;
aus:49.0
ein:b-a;
aus:-49.0

5 Programmierpunkte für neue yacc-Grammatik/lex Definition
5 Programmierpunkte für die Implementierung der Variablen Verwaltung. Um die volle Punktzahl zu bekommen ist eine Implementierung mittels Hash Funktion nötig.
2 Programmierpunkte für die Dokumentation

Abgabe bis: 10.1.03 per email an aufgabe22@btm2x2.mat.uni-bayreuth.de