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.