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?
- „Sie suchte den Nachtwächter mit der Laterne.“
- „Ich warte neben der Bank.“
- „Rudolf hat sich in München verliebt.“
Aufgabe 2
Gegeben sei die Grammatik mit den Terminalzeichen T= \{a, (, )\} und den Produktionen {P= \{S \rightarrow a \mid () \mid (S) \mid SS\}}.
Zeichnen Sie den Ableitungsbaum zum Wort (a)((aa)).
Aufgabe 3
Zeigen Sie, dass die folgende Grammatik mehrdeutig ist: P= \{S \rightarrow b \mid aS \mid Sa\}.
Aufgabe 4
Die Grammatik der vollständig geklammerten arithmetischen Terme hat die Regelmenge
P= {(T -> V | (TOT)),
(O -> + | - | * | /),
(V -> a | b | ... | z)}Leiten Sie drei verschieden komplexe Terme ab und zeigen Sie, dass diese Grammatik nicht mehrdeutig ist.
Aufgabe 5
Stellen Sie fest, welche der folgenden Worte Anweisungen im Sinne unserer Syntax sind. Gebe jeweils einen Ableitungsbaum an.
- 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
- while b do begin end
- begin begin begin v:=a end end end
- while b do v :=a ; if b then v:=a
Aufgabe 6
Bilde eine kontextfreie Grammatik für die Sprache L = \{a^{n}b^{n}c^{m} \mid n, m \in \mathbb{N} \}.
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)}