Aufgabe 1

Gibt es einen deterministischen 1-Weg Kellerautomaten, der genau die Menge aller Palindrome (über einem Alphabet mit mind. 2 Buchstaben) akzeptiert? Begründung!

Aufgabe 2

Sei G=({S,A,B},{0,1},P,S) mit P={ S::=ABA|BA, A::=0, B::=B01|eps} gegeben. Berechnen Sie die kanonische Kollektion J2 zu G. Ist J2 konsistent?

Aufgabe 3

Setzen Sie die Grammatik G = ( {E,D,F}, {a,+,*}, P, E )
mit P = { E::=E+D|D , D::=D*F|F , F::=(E)|a } als Eingabe für bison um, und beschreiben (ggf. zeichnen) Sie den erzeugten Analysator.

Hinweis: Option -v erzeugt eine beschreibende Ausgabe

Aufgabe 4

Setzen Sie den Teil <Ausdruck>der MML-Grammatik in bison-Eingabe um, und lassen Sie bison eine parser dafür erzeugen. Welche Probleme gibt es? Können Sie sie lösen?