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.