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

Abgabe bis Montag, 25. April 2005, 10:15 Uhr

5. (10 Punkte) Beschreiben Sie die Sprache L, die durch den regulären Ausdruck

0^{∗}(0 + 10^{∗}1)^{∗}(ε + 0 + 00)

gegeben ist. (Alle Worte in L haben eine sehr charakteristische Eigenschaft. Welche?) Beweisen Sie Ihre Behauptung! Gibt es einen einfacheren regulären Ausdruck für diese Sprache?

6. (0 Punkte)

(a) Geben Sie einen regulären Ausdruck an, der genau die Worte w über Σ mit der folgenden Eigenschaft beschreibt: ”w enthält keine zwei unmittelbar aufeinanderfolgenden gleichen Symbole,“ und zwar für Σ_{2} = {a, b}, Σ_{3} = {a, b, c}, und für Σ_{4} = {a, b, c, d}. Beweisen Sie, dass Ihr Ausdruck wirklich diese Sprache beschreibt!

(b) Lösen Sie dieselbe Aufgabe für die folgende Eigenschaft: ”Jedes Symbol in w steht neben einem gleichen Symbol.“ (Zum Beispiel hat das Wort aaabbcccaa diese Eigenschaft.)

(c) (schwierig) Wieviele Wörter der Länge n enthält die Sprache aus Aufgabe (b), für Σ_{2} und Σ_{3}?

7. (0 Punkte)

(a) Codieren Sie das Alphabet {a, b, …, z} durch Binärworte, so dass jedes codierte Wort wieder eindeutig decodierbar ist! (Eine ungeeignete Codierung wäre z.B. a ↦ 0, b ↦ 01, c ↦ 100, etc. In diesem Fall könnte nämlich 0100 von ac oder von baa herstammen.) Zeigen Sie, dass Ihre Codierung die gewünschte Eigenschaft hat.

(b) Das Alphabet Σ = {a, b} sei durch a ↦ 0 und b ↦ 010 codiert. Zeigen Sie, dass diese Codierung eindeutig decodierbar ist!

8. (Zusatzfrage, 10 Punkte) Welche der folgenden Gleichungen gelten für alle regulären Ausdrücke?

(a) (AB)C = A(BC)

(b) (A^{∗})^{∗} = A^{∗}

(c) (A + B)^{∗} = A^{∗} + B^{∗}

(d) (A^{∗}B^{∗})^{∗} = (A + B)^{∗}

Beweisen Sie Ihre Antworten.Wenn eine Beziehung nicht als Gleichung gilt, in welchen Fällen gilt dann eine Inklusionsbeziehung (⊆ oder ⊇)?

9. (0 Punkte) Geben sie einen regulären Ausdruck an, der alle Wörter über Σ = {0, 1} beschreibt, die 0101 nicht als Teilwort enthalten.

10. (0 Punkte) Konstruieren Sie einen regulären Ausdruck für die Sprache L_{1} der Wörter über {0, 1}, bei denen auf jedes Vorkommen der Teilfolge 0011 unmittelbar die Teilfolge 1100 anschließt.

Zum Beispiel ist w_{1} = 0001111100 ∉ L_{1}, w_{2} = 01011001111001111000 ∈ L_{1}, w_{3} = 0010 ∈ L_{1}, und w_{4} = 00111100011 ∉ L_{1}. Erklären Sie Ihren Ausdruck. (Ein formaler Korrektheitsbeweis ist nicht erforderlich.)