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

Abgabe bis Montag, 7. Mai 2001

7. (0 Punkte) Entscheiden Sie, ob die folgenden regulären Ausdrücke jeweils dieselbe Sprache darstellen.

(a) ε^{∗} = ε  (b) (01)^{∗}0 = 0(10)^{∗}  (c) ∅^{∗} = ε + (0 + ε)^{∗}∅

(d) A^{∗} = ε + A^{∗}A, wobei A ein beliebiger regulärer Ausdruck ist.

(e) (01^{∗})^{∗} = (01^{∗}0 + 0)^{∗} (f) (00)^{∗} + (00000)^{∗} + (000)^{∗} = 00^{∗}

8. (6 Punkte) Eine Kongruenzrelation ∼ auf einer Menge Σ^{∗} von Wörtern ist eine Äquiva-

lenzrelation mit folgender zusätzlicher Eigenschaft:

a ∼ b ∧ c ∼ d ⟹ ac ∼ bd.

Welche der folgenden Relationen sind Kongruenzrelationen? (Beweisen Sie Ihre Antworten.)

(a) (0 Punkte) a ∼ b ⟺ a und b haben die gleiche Anzahl von Nullen und die gleiche Anzahl von Einsen.

(b) (0 Punkte) a ∼ b ⟺ a = ε oder b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(c) (3 Punkte) a ∼ b ⟺ a = b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(d) (3 Punkte) a ∼ b ⟺ das Teilwort 01 kommt in a und b gleich häufig vor.

9. (5 Punkte) Für einen Zustand q ∈ Q des DEA M = (Q, Σ, δ, q_{0}, F) sei die Sprache L_{q}(M)

so definiert:

L_{q}(M) = { w ∈ Σ^{∗} | δ(q_{0}, w) = q }

Beweisen Sie: Wenn w_{1}, w_{2} ∈ L_{q}(M) sind, dann gilt für alle x ∈ Σ^{∗}:

w_{1}x ∈ L(M) ⟺ w_{2}x ∈ L(M)

10. (5 Punkte) Konstruieren Sie, wenn möglich, DEA’s, die folgende Sprachen über dem Alphabet {0, 1} akzeptieren.

(a) (3 Punkte) (0 + 1)^{∗}010101(0 + 1)^{∗}

(b) (2 Punkte) Alle Wörter, die das Teilwort 010101 nicht enthalten.

(c) (0 Punkte) Alle Wörter, die das Teilwort 01, aber nicht das Teilwort 100 enthalten.

(d) (0 Punkte) Alle Wörter, die gleich viele Nullen und Einsen enthalten.

(e) (0 Punkte) Alle Wörter, die das Teilwort 010 genau einmal enthalten.

(f) (Zusatzfrage, 3 Punkte) Beweisen Sie, dass jeder Automat, der Aufgabe (a) löst, mindestens sechs Zustände haben muss. [ Hinweis: Sie können Aufgabe 9 verwenden. ]

11. (0 Punkte) Konstruieren Sie, wenn möglich, DEA’s, die folgende Sprachen akzeptieren.

(a) Die durch 5 teilbaren Dezimalzahlen.

(b) Die durch 9 teilbaren Dezimalzahlen.

(c) Die durch 7 teilbaren Dezimalzahlen.

Untersuchen Sie dabei jeweils beide Möglichkeiten der Reihenfolge, in der die Dezimalstellen der Zahl eingegeben werden können: mit der höchsten Stelle zuerst oder mit der Einerstelle zuerst.