Grundlagen der theoretischen Informatik, SS 2005 Nachklausur zur Abschlussklausur

Abgabe bis Dienstag, 18. Oktober 2005, 19:30 Uhr

Aufgabe 1 2a 2b 3
Punkte 10 5 5 10
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt. Verwenden Sie gegebenenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie haben 90 Minuten Zeit.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Wandeln Sie die Grammatik

\begin{matrix}S → a+S | Ba \\ B → aBa | +a \end{matrix}

in Chomsky-Normalform um. Prüfen Sie dann mit dem CYK-Algorithmus nach, ob das Wort a+aa+aaa von dieser Grammatik erzeugt wird. Geben Sie gegebenenfalls einen Syntaxbaum (für die ursprüngliche Grammatik) an.

2. (a) (5 Punkte) Skizzieren Sie einen Algorithmus für das Wortproblem für Typ-1-

Sprachen. (etwa 5 Sätze)

(b) (5 Punkte) Beweisen Sie: Die Vereinigung einer kontextfreien Sprache und einer regulären Sprache ist kontextfrei.

3. Die Grammatik

\begin{matrix}S → S + S | S ∗ S | (S) | Z \\ Z → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 \end{matrix}

für einfache arithmetische Ausdrücke mit einzelnen Ziffern als Operanden ist mehrdeutig, weil zum Beispiel für den Ausdruck 3 + 4 ∗ 5 aus der Grammatik nicht hervorgeht, ob 3 + 4 oder 4 ∗ 5 zuerst berechnet werden soll.

(a) Geben Sie alle möglichen Syntaxbäume und alle möglichen Linksableitungen für das Wort 3 + 4 ∗ 5 an.

(b) Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass die Multiplikation (∗) stärker bindet als die Addition (+). Das Beispiel wird also so interpretiert, dass 3 + 4 ∗ 5 = 3 + 20 = 23 herauskommt, wenn man es ausrechnet. Schreiben Sie eine äquivalente eindeutige Grammatik, die diese Regel widerspiegelt.