Grundlagen der theoretischen Informatik, SS 2005 Zwischenklausur, Montag, 6. Juni 2005

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

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) Welche dieser Aussagen sind wahr? Geben Sie einen Beweis oder ein Gegenbeispiel an.

(a) (3 Punkte) Wenn L entscheidbar ist, dann ist auch L^{∗} entscheidbar.

(b) (3 Punkte) Wenn L unentscheidbar ist, dann ist auch L^{∗} unentscheidbar.

(c) (4 Punkte) Wenn L rekursiv aufzählbar ist, dann ist auch L^{∗} rekursiv aufzählbar.

2a. (5 Punkte) Definieren Sie, was ein regulärer Ausdruck über einem Alphabet Σ ist.

2b. (5 Punkte) Was ist die kleinste Sprache L, für die

L = {0, 01} ∪ L · {000, 111}

ist? Geben Sie einen regulären Ausdruch für L an.

3. (10 Punkte) Konstruieren Sie den Minimalautomaten für die folgende Sprache L ⊂ {0, 1}^{∗}:

L = { w | w enthält eine ungerade Anzahl von Einsen, und direkt vor jeder Eins steht eine Null }

Begründen Sie in 1–2 Sätzen, warum Ihr Automat diese Sprache akzeptiert. Wenn Sie den Automaten nicht durch den Minimierungsalgorithmus konstruiert haben, dann beweisen Sie auf andere Art, dass es der Minimalautomat ist.

Grundlagen der theoretischen Informatik, SS 2005 Nachklausur zur Zwischenklausur, Montag, 4. Juli 2005

Aufgabe 1a 1b 2 3
Punkte  5 5 10 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) Welche dieser Probleme sind entscheidbar? Begründen Sie Ihre Antworten, indem Sie entweder einen Lösungsalgorithmus oder einen Nichtentscheidbarkeitsbeweis in groben Zügen skizzieren.

(a) (5 Punkte) Gegeben sind zwei reguläre Ausdrücke R und S. Stellen diese beiden Ausdrücke dieselbe Sprache dar?

(b) (5 Punkte) Gegeben ist eine Turingmaschine M. Akzeptiert M alle Wörter? (also die Sprache Σ^{∗})

2. (10 Punkte) Betrachten Sie den nichtdeterministischen endlichen Automaten M mit Q = {a, b, c}, Σ = {0, 1}, Q_{0} = F = {a}, und mit

δ = {(a, 0, a), (a, 0, b), (b, 1, b), (b, 1, c), (c, 0, c), (c, 0, a)}.

Zeichnen Sie das Zustandsdiagramm, und konstruieren Sie einen dazu äquivalenten deterministischen Automaten, und den Minimalautomaten. (Der Minimalautomat ist immer ein deterministischer Automat.)

3. (10 Punkte) Konstruieren Sie einen endlichen Automaten ohne ε-Übergänge, der

die Sprache

(a + ba)^{∗}(b + ab)^{+} + (aa)^{∗}b(aaa)^{∗}

akzeptiert.

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.

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.