Grundlagen der theoretischen Informatik, SS 2005 Abschlussklausur

Abgabe bis Montag, 11. Juli 2005, 11:45 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) Geben Sie für die folgende kontextfreie Grammatik über dem Terminalalphabet Σ = {1, 2, 3} einen äquivalenten Kellerautomaten an. Entscheiden Sie selbst, ob der Automat deterministisch oder nichtdeterministisch ist, und wie der Automat akzeptieren soll.

\begin{matrix}S → SSS | A \\ A → A1A | AS2 | 3 \end{matrix}

2. (a) (5 Punkte) Formulieren Sie wahlweise das Pumping-Lemma für kontextfreie Sprachen oder das Pumping-Lemma für reguläre Sprachen.

(b) (5 Punkte) Beweisen Sie, dass die Sprache aller Doppelwörter

{ ww | w ∈ {0, 1}^{∗} }

nicht kontextfrei ist.

3. (10 Punkte) Wandeln Sie die Grammatik

S → aS | aAAS | B
A → Sb | aSb | ε
B → bA | AS

in Chomsky-Normalform um.