|
Compilerbau WiSe 2002/03
Übungsblatt 5
|
Aufgabe 1
Geben Sie einen deterministischen Kellerautomaten (KA) an, der die Wörter der Sprache L(KA)={w |w = vcv°, v aus {0, 1}*}
akzeptiert. Dabei soll v°
die Umkehrung des Wortes v bedeuten - die Wörter sind also Palindrome.
Kann auf das c
dabei verzichtet werden?
Aufgabe 2
Sei mit Anz(a,w)
die Anzahl der Vorkommen des
Zeichens a
im Wort w
bezeichnet.
Zeigen Sie: Die Sprache L = {w aus {a,b,c}* |
Anz(a,w)=Anz(b,w)=Anz(c,w)}
ist nicht kontextfrei.
Aufgabe 3
Gegeben sei eine Grammatik
G=({S,A,B,C,E},{a,b,e,f,l,p},P,S)
mit folgenden Produktionen:
S->AA|BB|C|Sl A->aC|ε|aAB
B->bBA|bBB C->pE|BC|E|AE
E->C|fe|ε|BB
Geben Sie eine aequivalente Grammatik
- ohne Epsilonproduktionen
- ohne Kettenproduktionen
- ohne nutzlose Symbole
an.
Dietmar Lammers
Last modified: So Nov 23 22:54:26 CET 2003