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.