FAMILIENNAME:  Vorname:  Matrikelnummer:

Grundlagen der theoretischen Informatik, SS 2001 erste Nachklausur zur 1. Klausur, Mittwoch, 25. Juli 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. (a) (3 Punkte) Konstruieren Sie einen endlichen Automaten, der die durch 5 teil-

baren Binärzahlen akzeptiert.

(b) (7 Punkte) Konstruieren Sie einen endlichen Automaten (ohne ε-Übergänge) für die Sprache

L = { w0 | w ist durch 5 teilbar } ∪ { w1 | w ist durch 7 teilbar }.

”w ist durch 5 teilbar“ bedeutet, dass w ∈ {0, 1}^{∗} ein Vielfaches von 5 ist, wenn man es als Binärzahl interpretiert.

Erläutern Sie Ihre Konstruktionen durch wenige Sätze.

2. (10 Punkte) Beweisen Sie, dass die regulären Sprachen unter Teilfolgenbildung abgeschlossen sind: Wenn L regulär ist, dann ist auch

L′ = { x | es gibt ein y ∈ L, sodass x Teilfolge von y ist }

regulär. Ein Wort x ∈ Σ^{∗} ist Teilfolge von y = y_{1}y_{2} … y_{n}, (y_{i} ∈ Σ) wenn x = y_{i_{1}}y_{i_{2}} … y_{i_{k}} für 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n, k ≥ 0, ist.

3. (10 Punkte) Zeichnen Sie das Zustandsdiagramm des nichtdeterministischen endlichen Automaten M = ({a, b}, {0, 1}, δ, {a}, {b}) mit

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

Bestimmen Sie einen dazu äquivalenden deterministischen endlichen Automaten. Bestimmen Sie einen Automaten, der die komplementäre Sprache {0, 1}^{∗} − L(M) akzeptiert. Geben Sie einen regulären Ausdruck für L(M) an.

4. (Zusatzfrage, 5 Punkte) Ist für jede reguläre Sprache L_{1} über dem Alphabet Σ = {0, 1} auch die Sprache

L_{2} = { w ∈ Σ^{∗} | 01001w ∈ L_{1} }

regulär? Beweisen Sie Ihre Antwort.