Grundlagen der theoretischen Informatik, SS 2005 — 3. Übungsblatt

Abgabe bis Montag, 9. Mai 2005, 10:15 Uhr

19. (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.

20. (a) Das Produkt von Automaten.

Konstruieren Sie zu zwei gegebenen DEAs M^{1} = (Q^{1}, Σ, δ^{1}, q_{0}^{1}, F^{1}) und M^{2} = (Q^{2}, Σ, δ^{2}, q_{0}^{2}, F^{2}) einen DEA für die Sprache L(M^{1}) ∩ L(M^{2}).

(b) Konstruieren Sie einen DEA für die Sprache L(M^{1}) ∪ L(M^{2}).

21. (a) Konstruieren Sie einen deterministischen endlichen Automaten, der die durch 5 teilbaren Binärzahlen akzeptiert. Diesmal soll das niederwertigste Bit als erstes gelesen werden.

(b) Konstruieren Sie endliche Automaten für die durch 6 teilbaren Dezimalzahlen, die (1) von der höchsten zur niedrigsten Stelle (2) von der niedrigsten zur höchsten Stelle gelesen werden.

22. Ist die Nerode-Relation einer Sprache L immer eine Kongruenzrelation? Ist die Nerode-Relation einer regulären Sprache L immer eine Kongruenzrelation?

23. Welche der folgenden Sprachen über Σ = {0, 1} sind regulär?

(a) Die Sprache L_{1} = { x | x = x^{R} } der Palindrome

(b) L_{2} = { 0^{i^{2}} | i ≥ 1 }

(c) L_{3} = { x | x enthält mindestens so viele Nullen wie Einsen }

(d) L_{4} = { x | die Anzahl der Nullen von x unterscheidet sich um höchstens um 1 von der Anzahl der Einsen }

(e) L_{5} = { x | in jedem Präfix von x unterscheidet sich die Anzahl der Nullen höchstens um 1 von der Anzahl der Einsen }

(f) L_{6} = { x | in jedem Präfix von x unterscheidet sich die Anzahl der Nullen höchstens um 2 von der Anzahl der Einsen }

24. (Zusatzaufgabe, 0 Punkte) Für einen Homomorphismus h: Σ^{∗} → Δ^{∗} und eine Sprache L ⊆ Σ^{∗} bezeichnet h(L) die Sprache

h(L) := { h(x) | x ∈ L }.

Beweisen Sie, dass das Bild h(L) einer regulären Sprache L unter einem Homomorphismus h regulär ist.

25. (*) Beweisen Sie: Wenn L ∈ Δ^{∗} regulär ist und h: Σ^{∗} → Δ^{∗} ein Homomorphismus ist, ist auch die folgende Sprache regulär:

h^{−1}(L) := { x ∈ Σ^{∗} | h(x) ∈ L }

26. Welche der Sprachen h_{j}(L_{i}) sind regulär, wenn L_{i} eine der Sprachen aus Aufgabe 23 ist und der Homomorphismus h_{j} folgendermaßen gegeben ist?

(a) h_{1}(0) = a, h_{1}(1) = b, Δ = {a, b}.

(b) h_{2}(0) = 1, h_{2}(1) = 1.

(c) h_{3}(0) = 01, h_{3}(1) = ε.

27. Konstruieren Sie den Minimalautomaten für den Automaten aus Aufgabe 15.