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.

Lösung:

1. Zunächst benötigt man n Reduktionen, um einstellige Terminalsymbole in einstellige Nichtterminale zu reduzieren. Dann benötigt man jeweils eine Reduktion, um aus zwei Nichtterminalen ein Nichtterminal zu reduzieren - also die verbleibende "Wortlänge" m um 1 zu verkürzen. Da das Startsymbol übrigbleibt, muß man das (n-1)-mal machen, insgesamt

   	  k = n + (n-1) = 2n - 1
   	  

2. Die Reduktion der Terminalsymbole auf die zugeordneten Nichtterminale kann man auf jeden Fall parallel machen. Danach ist der worst case offenbar, wenn pro Ebene des Strukturbaums nur eine Reduktion stattfinden kann (und das ist auch erreichbar, man denke sich eine kleines Beispiel aus!). Ergibt, mit den obigen Überlegungen, an notwendigen Baumebenen:

   	  1 + (n-1) = n
   	  

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.
In der Originalaufgabe war versehentlich C::=aB|B angegeben worden. Wir behandeln hier die o.g. Aufgabe.

Lösung:

Man kann das natürlich "von Hand" machen, und hoffen, das man es richtig macht. Besser ist, man folgt den folgenden Algorithmen:
Zunächst machen wir die Grammatik eps-frei, indem wir alle eps streichen und für alle Produktionen, in denen auf der rechten Seite Nichtterminale stehe, die zu eps abgeleitet werden konnten, Produktionen ohne diese Nichtterminale hinzufügen:

P1 = { S::=AB|CA , A::=DE , A::=E , B::=BC|AB , C::=aB|b , E::=A|a }

Dann entfernen wir alle nutzlosen Symbole, also alle Nichtterminale, die nicht zu Wörtern führen, mit folgendem Algorithmus (nach Aho/Ullman, The Theory of Parsing, Translation and Compiling, 143ff). Wir bauen dazu die Nichtterminalsymbole neu auf, indem wir zunächt die "von unten", also von den Terminalen erreichbaren, hinzunehmen, von denen dann die "von oben", also vom Startsymbol, herleitbaren verwenden:

Wir konstruieren induktiv die Menge der Nichtterminale neu. Sei ein KFG G=(N,T,P,S) gegeben. Wir definieren N0:={}, und i=1; Dann setzen wir solange Ni:= {A | A::=a ist aus P und a ist aus (Ni-1U T)*} U Ni-1, bis Ni=Ni-1 erreicht ist.

Hier: N1={C,E}, N2={A,C,E}, N3={S,A,C,E}, N4={S,A,C,E}.

Damit wird N4 unser neues N1, und wir müssen noch die Produktionen um die bereinigen, die nicht mehr verfügbare Symbole benutzen: P2 = { S::=CA , A::=E , C::=b , E::=A|a }

Nun müssen wir ggf. aus G2=(N1,T,P2,S) noch unerreichbare Symbole entfernen.

Wir konstruieren (wieder induktiv) die Menge der erreichbaren Symbole V (Nichtterminale und Terminale), beginnen aber mit V0:={S}. Dann bestimmen wir Vi:= {X | es gibt A::=aXb in P und A ist aus Vi-1} U Vi-1 und iterieren wieder solange, bis Vi=Vi-1 ist. Dann bereinigen wir die Mengen durch Schnitt mit der resultierenden Vi, so daß nur noch erlaubte Symbole und Produktionen vorkommen, und erhalten G3=(N2,T1,P3,S).

In diesem Fall: V0:={S}, V1:={S,C,A}, V2:={S,C,A,b,E}, V3:={S,C,A,b,E,a}, V4:={S,C,A,b,E,a}, also ist hier G3=G2.

Bleibt die Entfernung der Kettenproduktionen, die darauf hinausläuft, die 'single Produktions' zu entfernen, also die Reglen, dessen rechte Seite aus genau einem Nichtterminal besteht. Algorithmus:

Für alle A aus N wird iterativ die Menge der aus A herleitbaren Nichtterminale NA konstruiert:

1. N0={A}, und i:=1
2. Ni={C|B->C ist in P, C ist aus N, und B ist aus Ni-1} U Ni-1
3. Führe das Verfahren fort, bis Ni=Ni-1. Dann setze NA:=Ni

Dann konstruieren wir die neuen Produktionen P4 so: Wenn B->alpha aus P3 ist, und es ist keine Single-Produktion, dann nehme für alle A aus NBdie Regel A->alpha in P4 auf.

Hier:

NS:={S}, NA:={A,E}, NC:={C}, NE:={E,A}, also

betr. S::=CA: P41 = {S::=CA}
betr. C::=b: P42 = {S::=CA,C::=b}
betr. E::=a: P43 = {S::=CA,C::=b,A::=a,E::=a}

Jetzt müssen wir noch einmal unerreichbare Symbole entfernen, und erhalten schließlich:

G4=({S,A,C},{a,b},P5,S) mit P5={ S::=CA, C::=b, A::=a }

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!

Lösung:

Das ist eine Bastelaufgabe, die unterschiedlich ausfallen kann. Man sollte solche oder ähnliche Aufgaben zur Übung lösen, damit man mit den Techniken (reg. Ausdrücke, KFG) vertraut wird. Eine mögliche einfache Herangehensweise:

  Liste ::= Zeile | Zeile Liste
  Zeile ::= Autoren STOP Titel STOP Jahr STOP Verlag
  Autoren ::= Autor | Autor ', ' Autoren
  Titel ::= Wörter
  Verlag ::= Wörter
  Jahr ::= ZAHL
  Wörter ::= WORT | WORT Wörter
      

mit den aus der lexikalischen Analyse stammenden Terminalen STOP, ZAHL und WORDS aus (in lex-ähnlicher Angabe):

 ' '+*::' '+        liefert STOP
 [0-9]+             liefert ZAHL
 [A-Za-zäöüÄÖÜ-]+   liefert WORT
      

In dieser Form dürfen noch mehr Leerzeichen die Felder trennen, aber Jahresangaben dürfen noch sehr merkwürdig sein - da kann man naoch einiges verbessern!

Aufgabe 4

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

Lösung:

Man kann das folgendermassen angehen: Eine Binärzahl kann man von links lesen. Der Wert ist dann der bereits gelesene Wert, mit zwei multipliziert, plus 1, falls man dann eine 1 liest, und plus 0 sonst. (Bsp: (110)2 = (1*2+1)*2+0 = 6). Ein Automat kann nun die Reste bei Dision durch 3 betrachten (mod 3-Rechnung):
Ist der Rest 0 (Zustand q0), war der Wert durch 3 teilbar. Lese ich dann eine 0, bleibt er das - und der Zustand bleibt q0. Lese ich eine 1, bleibt ein Rest von 1, und wir gehen in den Zustand q1, unsere gelesenen Zahl ist x=n*3+1.
Lesen wir aus q1 eine 1, erhalten wir x2=2*x+1=2*n*3+2*1+1=2*(n+1)*3, also einen Rest 0, und wir wechseln wieder nach q0. Lesen wir aus q1 eine 0, erhalten wir x2=2*x+0=2*n*3+2*1=m*3+2, also einen Rest 2, und wechseln in den Zustand q2.
Lesen wir aus q2 eine 1, erhalten wir x3=2*x2+1=2*(m*3+2)+1=k*3+2, wir bleiben also im Zustand q2. Lesen wir eine 0, erhalten wir x3=2*x2+0=2*(m*3+2)+0=l*3+1, also Rest 1, und wir wechseln wieder in Zustand q1. Der entsprechende Automat A = ({q0,q1,q2},{0,1},d,q0,{q0})

      d(q0,0) = q0     d(q1,0) = q2    d(q2,0) = q1
      d(q0,1) = q1     d(q1,1) = q0    d(q2,1) = q2
      

Man kann das auch allgemeiner zeigen siehe z.Bsp. van Leeuven, Handbook of theoretical computer science Vol B, pp 36.