Prof. Dr. Hans-Jörg Kreowski, Dr. Sabine Kuske 28. April 2003 Studiengang Informatik Aufgaben 1 MZH 3260, 3180 Tel.: 2956, 2335, 3697 (Sekr.), Fax: 4322 E-Mail: {kreo,kuske}@informatik.uni-bremen.de

Theoretische Informatik II

1. Übungsblatt

Geübt wird der Umgang mit Zeichenketten, wie sie im Kapitel 2 des Skripts zur Theoretischen Informatik 1 definiert sind. Alle Teilnehmerinnen und Teilnehmer sollten sich mit diesem Stoff noch einmal beschäftigen, weil Mengen von Zeichenketten der zentrale Gegenstand dieser Lehrveranstaltung sind. Für diejenigen jedoch, die im vorigen Semester den Leistungsnachweis erworben haben, ist dieses Übungsblatt keine Pflicht. Auf der Basis der Konkatenation lassen sich zwei Operationen auf Mengen von Zeichenketten definieren. Für L, L′ ⊆ A^{∗} sind die Konkatenation von L und L′ sowie das L′-Derivat von L gegeben durch:

• L · L′ = {uv | u ∈ L, v ∈ L′}

• L/L′ = {w | uw ∈ L für ein u ∈ L′}.

Ist L oder L′ einelementig, kann man L bzw. L′ durch das Element ersetzen, also u · L′ für {u} · L′, L · v für L · {v} und L/v für L/{v}. Betrachte nun die Menge aller Wörter über dem Alphabet {a, b}, die gewichtet gleich viele a’s wie b’s enthalten:

L_{2|3} = {w ∈ {a, b}^{∗} | 2 · count(a, w) = 3 · count(b, w)}

und löse folgende Aufgaben:

1. Welche der folgenden Wörter sind Elemente von L_{2|3}: λ, ababa, babab, a^{6}b^{4}c, a^{6}b^{4}, b^{6}a^{9}, b^{7}a^{3}b^{3}a^{12}, a^{k}b^{l} mit l = \frac{2}{3}k und k mod 3 ≠ 0? (10%)

2. Gib alle Elemente von L_{2|3} der Länge 5 an. (10%)

3. Zeige uv ∈ L_{2|3}, falls u, v ∈ L_{2|3}. (10%)

4. Zeige length(u) mod 5 = 0 für alle u ∈ L_{2|3}. (15%)

5. Zeige L_{2|3}/a ≠ L_{2|3}/b. (10%)

6. Zeige L_{2|3}/a^{i} ≠ L_{2|3}/a^{j} für i ≠ j. (15%)

7. Zeige, dass für alle u ∈ {a, b}^{∗} gilt:

(a) L_{2|3}/u = \{w ∈ \{a, b\}^{∗} | count(b, w) = \frac{2}{3} (count(a, w) + count(a, u)) − count(b, u)} (10%)

(b) L_{2|3}/u ist unendlich. (20%)

Die bearbeiteten Übungsaufgaben sind spätestens in der Woche vom 12.5.2003 in den Tutorien abzugeben.