Übung Kontextfreie Sprachen

---

Aufgabe 1

Sätze natürlicher Sprachen können mehrdeutig sein, was ihr Verständnis erschwert. Man unterscheidet zwischen lexikalischer und struktureller Mehrdeutigkeit.

• Von lexikalischer Mehrdeutigkeit spricht man, wenn ein Wort mehrere Bedeutungen besitzt. Der Satz "Das Schloss wurde im 16. Jahrhundert gebaut" beispielsweise kann sich entweder auf ein Gebäude oder eine Schließvorrichtung beziehen.
• Bei struktureller Mehrdeutigkeit besitzt ein Satz zwei verschiedene Syntaxbäume und damit möglicherweise auch zwei verschiedene Bedeutungen.

Welche Art von Mehrdeutigkeit liegt bei folgenden Sätzen vor?

1. "Sie suchte den Nachtwächter mit der Laterne."
2. "Ich warte neben der Bank."
3. "Rudolf hat sich in München verliebt."

---

Aufgabe 2

Gegeben sei die Grammatik mit den Terminalzeichen T= {a, (, )} und den Produktionen P= {S -> a | () | (S) | SS}. Zeichne den Ableitungsbaum zum Wort (a)((aa)).

---

Aufgabe 3

Zeige, dass die folgende Grammatik mehrdeutig ist: P= {S -> b | aS | Sa}.

---

Aufgabe 4

Die Grammatik der vollständig geklammerten arithmetischen Terme hat die Regelmenge

P= {(T -> V | (TOT)),
    (O -> + | - | * | /),
    (V -> a | b | ... | z)}

Leite drei verschieden komplexe Terme ab und zeige, dass diese Grammatik nicht mehrdeutig ist.

---

Aufgabe 5

Stelle fest, welche der folgenden Worte Anweisungen im Sinne unserer Syntax sind. Gebe jeweils einen Ableitungsbaum an.

1. begin begin if b then v:=a ; while b do begin v:=a ; end; end; begin while b do begin v:=a ; v:=a ; v:=a end end end end
2. while b do begin end
3. begin begin begin v:=a end end end
4. while b do v :=a ; if b then v:=a

---

Aufgabe 6

Bilde eine kontextfreie Grammatik für die Sprache $L_1=\lbrace a^nb^nc^m~|~n,m \in N\rbrace$.

---

Aufgabe 7

Ist die Grammatik mit den folgenden Produktionen kontextfrei? Bestimme die Sprache, die sie erzeugt.

P = {(S -> aB | aSA),
     (B -> bc),
     (cA -> Ac),
     (BA -> bBc)}