Aufgabe 1

Sei eine Grammatik G=(N,T,P,S) in Chomsky-Normalform gegeben und w ein Wort aus L(G) mit |w|=n.

1. Gelte S ->kw. Bestimmen Sie k.
2. Geben Sie eine Abschätzung für die maximale Tiefe des Strukturbaums der Ableitung von w an.

Aufgabe 2

Geben Sie zu G=({A,B,C,D,E},{a,b},P,S) mit P={ S::=AB|CA, A::=DE, B::=BC|AB, C::=aB|B, D::=eps, E::=A|a} eine äquivalente kontextfreie Grammatik an, die keine nutzlosen Symbole, keine Ketten- und eps-Produktionen enthält.

Aufgabe 3

Gegeben sei eine Bücherliste der Form

        Author :: Titel :: Erscheinungsjahr :: Verlag
      

also beispielsweise

      Aho,Sethi,Ullman :: Compilerbau :: 1988 :: Addison-Wesley
      Helmut Kopka :: LaTeX - Eine Einführung :: 1991 :: Addison-Wesley
      

Sie wollen diese, als Textdatei vorliegende Liste, in eine html-Version verwandeln, und dafür Techniken des Compilerbaus verwenden. Wie gehen Sie vor? Geben Sie Tokenklassen und Automaten für die lexikalische Analyse, und eine Grammatik für die syntaktische Analyse an!

Aufgabe 4

Geben Sie einen endlichen Automaten an, der alle Vielfachen von 3 in binärer Darstellung akzeptiert.