FAMILIENNAME:  Vorname:  Matrikelnummer:

Grundlagen der theoretischen Informatik, SS 2001 zweite Nachklausur zum 1. Teil, Dienstag, 9. Oktober 2001

Aufgabe 1 2 3 (4)
Punkte 10 10 10 (5)
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf dem dafür vorgesehenen Blatt. Verwenden Sie gegebenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer.

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) L_{1} sei eine reguläre Sprache über dem Alphabet {0, 1}, und

L_{2} = { w_{1}0w_{2}0 … 0w_{n} | w = w_{1}w_{2} … w_{n} ∈ L_{1}, n ≥ 1, w_{i} ∈ {0, 1} }

sei die Sprache, wo zwischen je zwei Buchstaben eine Null eingefügt ist. (Am Ende wird keine Null angehängt!) Beweisen Sie, dass L_{2} ebenfalls regulär ist.

2. (10 Punkte) Betrachten Sie den nichtdeterministischen endlichen Automaten M = ({a, b, c}, {0, 1}, δ, {a}, {a}) mit

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

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)^{∗} + (bb)^{∗}a^{+}(bb)^{∗}

akzeptiert.

4. (Zusatzfrage, 5 Punkte) Ist das folgende Problem entscheidbar?

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

Begründen Sie Ihre Antwort, indem Sie entweder einen Lösungsalgorithmus oder einen Nichtentscheidbarkeitsbeweis in groben Zügen skizzieren.