Grundlagen der theoretischen Informatik, SS 2001 — 4. Übungsblatt

Abgabe bis Montag, 21. Mai 2001 (Abgabe in Dreiergruppen!)

19. (6 Punkte) Produkt von Automaten.

Wie kann man zu zwei gegebenen DEA M_{1} und M_{2} einen DEA konstruieren, der die Sprache L(M_{1}) ∩ L(M_{2}) akzeptiert? (Hinweis: Der neue Automat soll die Automaten M_{1} und M_{2} ”gleichzeitig“ simulieren; Welche Zustandsmenge muss er haben?)

20. (0 Punkte) Zeigen Sie: Wenn L = { x ∈ {0, 1}^{∗} | x enthält gleich vielen Nullen und Einsen } regulär wäre, dann wäre auch die Sprache L′ = { 0^{n}1^{n} | n ≥ 0 } regulär.

21. (4 Punkte) Konstruieren Sie einen NEA für die Sprache ε + 0 + ((01^{∗}0)^{∗} + 10^{∗})^{∗}.

22. (0 Punkte) Konstruieren Sie einen NEA für die Sprache (0 + 1)^{∗}000(0 + 1 + ε)^{∗}.

23. (6 Punkte) Bestimmen Sie den Minimalautomaten für den NEA aus Aufgabe 12.

24. (0 Punkte) Wie kann man für einen gegebenen DEA oder NEA M feststellen, ob L(M) = ∅ ist?

25. (0 Punkte) Beweisen Sie, dass die Klasse der regulären Sprachen abgeschlossen gegenüber Umkehrung ist: Wenn L regulär ist, dann ist auch L^{R} regulär. (L^{R} ist die Menge der von hinten gelesenen Wörter von L.)

Nächste Woche entfällt die Vorlesung, und es wird kein Übungsblatt ausgeteilt. Die Tutorien finden aber wie gewöhnlich statt.