Prof. Dr. R. Laue                                                                                                                                  WS9899
                                Informatik III
                                Übungsblatt 4
                                Abgabe: 30.11.98 in der Vorlesung

URL:         /axel/informatik3_ws9899_blatt4.html
Dieses  Übungsblatt ist alleine zu bearbeiten.
 

Aufgabe 10 (6 Punkte)
Man definiere für den Taschenrechner aus Aufgabe 8 eine Grammatik. Es ist zu beachten, daß mehrere durch ";"
getrennte Anweisungen erlaubt sind.

Aufgabe 11 (6 Punkte)
Man konstruiere zu folgendem Automaten A eine Grammatik G mit L(A) = L(G). A habe das Eingabealphabet
{a,b,c,d,e,f} und die Zustandmenge {1,2,3,4,5}, Startzustand sei 1 und die Finalmenge sei {4}, die Übergangsfunktion sei gegeben durch

a b c d e f
1 5 5 5 2 5 5
2 2 5 4 5 3 5
3 5 4 5 5 5 1
4 5 5 4 5 5 5
5 5 5 5 5 5 5

Aufgabe 12 (5+3 Punkte)
a) Sei
                                   G=({X} , {[,],x,#,^}, R, X)

mit
                    R={ X --> [X#X], X --> [X^X],  X-->[X] , X --> x}

eine Grammatik. Wieviel Ableitungen gibt es für

                                           [[[ x^x ]] #  [x#x]]?
Begründung.
b) Wir erweitern die Regelmenge R aus Teil a um die beiden Regeln:

                 X] --> [X          und        [X --> X]

Wieviel Ableitungen gibt es jetzt für das obige Wort? Begründung.