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

1. ohne Epsilonproduktionen
2. ohne Kettenproduktionen
3. ohne nutzlose Symbole

an.