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

Abgabe bis Dienstag, 5. Juni 2001

26. (4 Punkte) Welche der folgenden Sprachen über Σ = {0, 1} sind regulär? beweisen Sie Ihre Antworten.

(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 | jeder Präfix von x enthält mindestens so viele Nullen wie Einsen }

(e) (2 Punkte) L_{5} = { x | die Anzahl der Nullen von x unterscheidet sich um höchstens um 1 von der Anzahl der Einsen }

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

Ein Präfix ist dabei ein Anfangsstück eines Wortes: x ist Präfix von y, wenn y = xu für ein u ∈ Σ^{∗} ist.

27. (0 Punkte) Es seien Σ und Δ zwei Alphabete. Ein Homomorphismus h: Σ^{∗} → Δ^{∗} ist durch eine beliebige Funktion h: Σ → Δ^{∗} gegeben, die folgendermaßen auf Σ^{∗} erweitert wird:

h(x_{1}x_{2} … x_{n}) := h(x_{1})h(x_{2}) … h(x_{n}), für n ≥ 0, x_{1}, …, x_{n} ∈ Σ

Ein Homomorphismus ist durch folgende Eigenschaften charakterisiert:

h(ε) = ε, und h(x · y) = h(x) · h(y), für alle x, y ∈ Σ^{∗}

Für eine Sprache L ⊆ Σ^{∗} bezeichnet h(L) die Sprache

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

28. (4 Punkte) Welche der Sprachen h_{j}(L_{i}) sind regulär, wenn L_{i} eine der Sprachen aus Aufgabe 26 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) = ε.

Es gibt je 2 Punkte für die Sprachen h_{3}(L_{4}) und h_{2}(L_{1}).

29. (8 Punkte) Erweitern Sie das in der Vorlesung vorgestellte lex-Programm^{1} zur Addition aller in der Eingabe vorkommenden Zahlen um folgende Funktionen:

(a) Bei Eingabe des Zeichens * oder - wird die nächste Zahl nicht addiert, sondern multipliziert beziehungsweise subtrahiert. Bei Eingabe von = wird das bisherige Ergebnis ausgedruckt.

(b) Es werden zusätzlich auch Kommentare im Stil von Haskell verstanden: Alles zwischen -- und dem Ende der Zeile wird ignoriert.

Die obigen Angaben lassen einige Fragen offen, zum Beispiel den Unterschied zwischen Subtraktion (5 - 3) und einem negativen Vorzeichen (5 * -3). Ergänzen Sie zunächst die obige Aufgabenspezifikation in Worten, sodass das Verhalten des Programmes eindeutig daraus hervorgeht. Ihr Programm sollte dann dieser Spezifikation entsprechen.

1http://www.inf.fu-berlin.de/~rote/Lere/Grundlagen%20der%20theoretischen%20Informatik/flex/summe.flex