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

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

11. Kommutierende Wörter: Wieviele Paare von Wörter a ∈ Σ^{3} und b ∈ Σ^{2} mit der Eigenschaft ab = ba gibt es? Wieviele Paare von Wörter a ∈ Σ^{6} und b ∈ Σ^{9} mit der Eigenschaft ab = ba gibt es? Wie ist es allgemein für a ∈ Σ^{m} und b ∈ Σ^{n}? Wodurch kann man solche Wortpaare charakterisieren?

12. Eine Kongruenzrelation ∼ auf einer Menge Σ^{∗} von Wörtern ist eine Äquivalenzrelation mit folgender zusätzlicher Eigenschaft:

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

Welche der folgenden Relationen sind Kongruenzrelationen? Die Beziehung a ∼ b soll genau dann gelten, wenn folgende Bedingung erfüllt ist:

(a) a und b haben die gleiche Anzahl von Nullen und die gleiche Anzahl von Einsen.

(b) a = b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(c) a = ε oder b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(d) das Teilwort 100 kommt in a und b gleich häufig vor.

13. Schreiben Sie ein Programm in Haskell (oder Java), das für einen endlichen Automaten (in einer geeigneten Darstellung) und ein gegebenes Wort entscheidet, ob es vom Automaten akzeptiert wird.

14. (a) (5 Punkte) Konstruieren Sie einen endlichen Automaten, der die durch 5 teilbaren

Binärzahlen akzeptiert. Das höchstwertige Bit wird dabei zuerst eingelesen.

(b) (5 Punkte) Konstruieren Sie einen deterministischen endlichen Automaten, der genau jene Wörter über dem Alphabet {a, b, c, d} akzeptiert, die das Teilwort abacabadabaca enthalten.

(c) (0 Punkte) Konstruieren Sie einen endlichen Automaten, der die Wörter akzeptiert, die das Teilwort abacabadabaca nicht enthalten.

Erläutern Sie Ihre Automaten mit einigen Sätzen. Zeichnen Sie Zustandsdiagramme.

15. Konstruieren Sie einen äquivalenten deterministischen Automaten für den nichtdeterministischen endlichen Automaten mit Σ = {0, 1}, Q = {a, b, c}, Q_{0} = {a}, F = {a} und

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

16. (Zusatzaufgabe, 0 Punkte) Beweisen Sie, dass die von einem DEA akzeptierten Sprachen (die regulären Sprachen) unter Präfixbildung abgeschlossen sind: Wenn L eine solche Sprache ist, dann gibt es auch einen DEA, der

L′ = { x | es gibt ein y mit xy ∈ L }

akzeptiert.

17. Konstruieren Sie einen endlichen Automaten ohne ε-Übergänge für die Sprache

(a + ba)^{+}(b + ab)^{∗} + (bb)^{∗}a^{+}(bb)^{∗}.

18. 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)