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

Abgabe bis Montag, 30. April 2001

1. (0 Punkte) Sei Σ ein Alphabet mit k Elementen und n ∈ ℕ.

(a) Wieviele Worte in Σ^{∗} haben die Länge n?

(b) Wieviele Palindrome in Σ^{∗} haben die Länge n? (Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen gleich ist.)

(c) Wieviele Worte w ∈ {0, 1}^{∗}, die Binärdarstellung einer durch 5 teilbaren Zahl sind (führende Nullen sind erlaubt), haben die Länge n?

(d) Wie ist es, wenn führende Nullen verboten sind?

Jede Behauptung ist zu beweisen!

2. (0 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?

3. (6 Punkte)

(a) (0 Punkte) 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) (6 Punkte) 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) (Zusatzaufgabe, 2 Punkte) Wieviele Wörter der Länge n enthält die Sprache aus Aufgabe (b), für Σ_{2} und Σ_{3}?

4. (6 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!

5. (4 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. Zusatzfrage (2 Punkte): Wenn eine Beziehung nicht als Gleichung gilt, in welchen Fällen gilt dann eine Inklusionsbeziehung (⊆ oder ⊇)?

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

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.

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

Abgabe bis Montag, 14. Mai 2001

12. (6 Punkte) Zeichnen Sie das Zustandsdiagramm des NEA ({a, b, c, d, e}, {0, 1}, δ, {a}, {e}) mit δ = {(a, 0, a), (a, 1, a), (a, 0, b), (a, 1, c), (b, 0, b), (b, 1, d), (c, 0, d), (d, 1, e), (e, 0, e)}, und bestimmen Sie einen dazu äquivalenten DEA. Versuchen Sie, dabei mit möglichst wenigen Zuständen auszukommen.

13.

(0 Punkte) Konstruieren Sie für den DEA M = ({a, b, c}, {0, 1}, δ, a, {b}) einen regulären Ausdruck, der die von M akzeptierte Sprache beschreibt. Die Übergangsfunktion δ ist in der nebenstehenden Tabelle angegeben.

Wenden Sie den in der Vorlesung vorgestellten Algorithmus von Kleene auf die Zustände einmal in der Reihenfolge a, b, c und dann in der Reihenfolge c, a, b an. Vereinfachen Sie dabei die Zwischenergebnisse, so gut es geht. Versuchen Sie auch, ”direkt“ durch Betrachten des Zustandsdiagramms und Nachdenken einen möglichst einfachen regulären Ausdruck zu finden.

\begin{matrix}δ & 0 & 1 \\ a & a & b \\ b & c & b \\ c & b & a \end{matrix}

14. (5 Punkte) Im Beweis für die Äquivalenz zwischen endlichen Automaten und regulären Ausdrücken wird für die von einem gegebenen deterministischen endlichen Automaten akzeptierte Sprache ein regulärer Ausdruck konstruiert. Funktioniert diese Konstruktion auch für nichtdeterministische endliche Automaten? Wie muss man die Konstruktion in diesem Falle anpassen, oder an welcher Stelle ist es wesentlich, dass der Automat deterministisch ist?

15. (0 Punkte) Betrachten Sie deterministische sowie nichtdeterministische endliche Automaten (mit oder ohne ε-Übergänge), die nur einen einzigen akzeptierenden Zustand haben dürfen. Sind diese Automaten gegenüber allgemeinen endlichen Automaten in ihrer Mächtigkeit eingeschränkt? Gibt es reguläre Sprachen, die von solchen Automaten nicht erkannt werden können?

16. (3 Punkte) Manchmal werden nichtdeterministische endliche Automaten so definiert, dass Sie nur einen einzigen Anfangszustand haben. Zeigen Sie, dass diese Automaten gegenüber NEA’s mit beliebig vielen Anfangszuständen in ihrer Mächtigkeit nicht eingeschränkt sind und dieselbe Klasse von Sprachen akzeptieren.

(Zusatzfrage, 2 Punkte) Geben Sie eine möglichst einfache und sparsame Methode an, wie man aus einem beliebigen NEA einen äquivalenten NEA mit nur einem Anfangszustand konstruiert.

17. (0 Punkte) Konstruieren Sie DEAs und NEAs für folgende Sprachen über {0, 1}:

(a) die Wörter, deren vierter Buchstabe eine 1 ist;

(b) die Wörter, deren viertletzter Buchstabe eine 1 ist.

18. (0 Punkte) Gegeben seien zwei endliche Automaten M_{1} und M_{2}, die die Sprachen L_{1} beziehungsweise L_{2} akzeptieren. Konstruieren Sie endliche Automaten, die die Sprachen (a) L_{1} ∪ L_{2}, (b) L_{1} · L_{2}, (c) L_{1} ∩ L_{2} akzeptieren. Sie dürfen dabei wahlweise mit deterministischen oder mit nichtdeterministischen Automaten arbeiten, je nachdem, was Ihnen für die jeweilige Aufgabe günstiger erscheint.

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

Abgabe bis Montag, 21. Mai 2001 (Abgabe in Dreiergruppen!)

19. (6 Punkte) Produkt von Automaten.

Wie kann man zu zwei gegebenen DEA M_{1} und M_{2} einen DEA konstruieren, der die Sprache L(M_{1}) ∩ L(M_{2}) akzeptiert? (Hinweis: Der neue Automat soll die Automaten M_{1} und M_{2} ”gleichzeitig“ simulieren; Welche Zustandsmenge muss er haben?)

20. (0 Punkte) Zeigen Sie: Wenn L = { x ∈ {0, 1}^{∗} | x enthält gleich vielen Nullen und Einsen } regulär wäre, dann wäre auch die Sprache L′ = { 0^{n}1^{n} | n ≥ 0 } regulär.

21. (4 Punkte) Konstruieren Sie einen NEA für die Sprache ε + 0 + ((01^{∗}0)^{∗} + 10^{∗})^{∗}.

22. (0 Punkte) Konstruieren Sie einen NEA für die Sprache (0 + 1)^{∗}000(0 + 1 + ε)^{∗}.

23. (6 Punkte) Bestimmen Sie den Minimalautomaten für den NEA aus Aufgabe 12.

24. (0 Punkte) Wie kann man für einen gegebenen DEA oder NEA M feststellen, ob L(M) = ∅ ist?

25. (0 Punkte) Beweisen Sie, dass die Klasse der regulären Sprachen abgeschlossen gegenüber Umkehrung ist: Wenn L regulär ist, dann ist auch L^{R} regulär. (L^{R} ist die Menge der von hinten gelesenen Wörter von L.)

Nächste Woche entfällt die Vorlesung, und es wird kein Übungsblatt ausgeteilt. Die Tutorien finden aber wie gewöhnlich statt.

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

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

Abgabe bis Dienstag, 12. Juni 2001

30. (6 Punkte) Binäre Addition.

Konstruieren Sie eine Turingmaschine, die die Summe zweier Zahlen in Binärdarstellung berechnet. Bei Eingabe von bin(x)#bin(y)$ soll die Maschine mit der Ausgabe bin(x + y)#bin(y)$ und dem Kopf auf dem ersten Eingabesymbol halten. Dabei soll die Notation bin(x) ∈ {0, 1}^{∗} eine Darstellung von x ∈ ℕ in Binärdarstellung darstellen. Der Automat soll am Ende in einen Zustand q_{F} übergehen und anhalten. Ein eventueller Bandinhalt rechts vom $-Zeichen soll unverändert stehengelassen werden.

Beschreiben Sie Ihren Algorithmus zunächst in Worten.

Geben Sie die ersten 15 und die letzten 10 Konfigurationen Ihrer Turingmaschine bei Eingabe von 101#11$ an.

31. (0 Punkte) Multiplikation.

Konstruieren Sie eine Turingmaschine, die zwei ”unäre“ Zahlen multipliziert. Bei Eingabe von 0^{m}1^{n} soll die Ausgabe 0^{mn} berechnet werden.

32. (0 Punkte)

(a) Entwerfen Sie eine Turingmaschine, die die Sprache { 0^{n}1^{n}0^{n} | n ≥ 0 } akzeptiert.

(b) Entwerfen Sie eine Turingmaschine für dieselbe Sprache, die mit dem Bandalphabet Γ = {0, 1, B} auskommt. (Hinweis: Sie können ein größeres Bandalphabet ”simulieren“, indem Sie es ”binär kodieren“. Dabei wird jeweils eine feste Anzahl von Feldern des Bandes zu einer logischen Einheit zusammengefasst.)

33. (5 Punkte) Definieren Sie formal die Nachfolgerrelation xqy ⊢ x′q′y′ für Konfigurationen einer Turingmaschine. (q, q′ ∈ Q, x ∈ {ε} ∪ (Γ − {B})Γ^{∗}, y ∈ {ε} ∪ Γ^{∗}(Γ − {B}).)

34. (0 Punkte) Speicherzugriff (Tabellenzugriff) über Adressen.

(a) Lesen aus einer Tabelle.

Bei Eingabe von

x = #x_{1}|y_{1}#x_{2}|y_{2}# … #x_{n}|y_{n}$x_{0}

mit n ≥ 0, x_{k}, y_{k} ∈ {0, 1}^{∗} soll die Ausgabe x|y berechnet werden. Dabei ist y = y_{i} für den größten Index i ≤ n mit x_{i} = x_{0}, und y = 0, falls kein solches i existiert.

(b) Löschen aus einer Tabelle.

Bei den gleichen Angaben wie oben soll die Ausgabe

x = #x_{1}|y_{1}# … #x_{i−1}|y_{i−1}#x_{i+1}|y_{i+1}# … #x_{n}|y_{n}$x_{0}

berechnet werden. Wenn kein passender Index i existiert, soll die Eingabe unverändert gelassen werden.

35. (4 Punkte) Beweisen oder widerlegen Sie:

(a) (4 Punkte) Das Komplement einer entscheidbaren Sprache ist entscheidbar.

(b) (0 Punkte) Die Vereinigung zweier entscheidbarer Sprache ist entscheidbar.

(c) (0 Punkte) Das Komplement einer unentscheidbaren Sprache ist unentscheidbar.

(d) (0 Punkte) Die Vereinigung zweier unentscheidbarer Sprache ist unentscheidbar.

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

Abgabe bis Montag, 18. Juni 2001

36. (6 Punkte) Beweisen Sie:

(a) (6 Punkte) Wenn L_{1} und L_{2} entscheidbar sind, dann ist auch L_{1}L_{2} entscheidbar.

(b) Wenn L_{1} und L_{2} rekursiv aufzählbar sind, dann ist auch L_{1}L_{2} rekursiv aufzählbar.

37. (0 Punkte) Eine Sprache L ist genau dann entscheidbar, wenn sowohl die Sprache L als auch ihr Komplement L̄ rekursiv aufzählbar ist.

38. (0 Punkte)

(a) Zeigen Sie, dass die Sprache D̄ rekursiv aufzählbar ist.

(b) Zeigen Sie, dass die Sprache 0D ∪ 1D̄ nicht rekursiv aufzählbar ist. (D = { w_{i} | M_{i} akzeptiert w_{i} nicht } ist die Diagonalsprache und D̄ ihr Komplement.)

39. (2 Zusatzpunkte) Eine andere Konstruktion einer unentscheidbaren Sprache.

U′ := { ⟨M⟩w | M akzeptiert das Wort ⟨M⟩w nicht }

(Der Beweis geht ähnlich wie bei der Diagonalsprache D.)

40. (6 Punkte) Welche der folgenden Sprachen sind rekursiv, welche sind rekursiv aufzählbar? (a) (3 Punkte) L_{1} = { 0^{k}⟨M⟩w | M akzeptiert w nach höchstens k Schritten. }

(b) L_{2} = { 0^{k}⟨M⟩w | M hat w nach k Schritten noch nicht akzeptiert. }

(c) L_{3} = Σ^{∗} − (L_{1} ∪ L_{2})

(d) (3 Punkte) L_{4} = { 0^{k}⟨M⟩w | M akzeptiert w nach mehr als k Schritten. }

41. (4 Punkte) Beiweisen Sie, dass die Sprache L = { 0^{i} | i ≥ 0, das Teilwort 0^{i}123 kommt in der Dezimaldarstellung von π unendlich oft vor } entscheidbar ist. (Sie müssen dazu nichts über π wissen, nur logisch überlegen können. Wie kann L aussehen?)

42. (0 Punkte) Welche der folgenden Aussagen sind wahr, und welche sind falsch? Welche Aussagen sind trivial, und welche sind absurd?

(a) Jede Teilmenge einer rekursiven Sprache ist rekursiv.

(b) Jede Teilmenge einer rekursiv aufzählbaren Sprache ist rekursiv aufzählbar.

(c) Jede reguläre Sprache ist rekursiv aufzählbar.

(d) Jede Teilmenge einer regulären Sprache ist regulär. Weil noch etwas Platz ist, seien hier noch einmal die Kriterien für die Erlangung eines Übungsscheines in Erinnerung gerufen.^{1}

1. 60 % der Gesamtpunktezahl der Übungen. (Die Übungszettel können in Dreiergruppen oder in Zweiergruppen abgegeben werden.)

2. Bei jedem Übungszettel bis auf einen müssen mindestens 30 % der Punkte erreicht werden.

3. 50 % der Punkte bei der Zwischenklausur und 50 % der Punkte bei der Abschlussklausur (oder bei der entsprechenden Nachklausur).

4. Aktive Teilnahme an den wöchentlichen Tutorien und einmaliges Vorrechnen Der Schein wird benotet. Die Note ergibt sich aus den Klausuren.

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

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

Abgabe bis Montag, 25. Juni 2001

44. (5 Punkte) Beweisen Sie:

(a) (0 Punkte) Wenn es eine Turingmaschine gibt, die die Wörter einer Sprache in beliebiger Reihenfolge, möglicherweise mit Wiederholungen, auf ein Ausgabeband schreibt, dann ist diese Sprache rekursiv aufzählbar.

(b) (5 Punkte) Eine Sprache ist genau dann rekursiv, wenn es eine Turingmaschine gibt, die die Wörter der Sprache der Länge nach sortiert auf ein Ausgabeband schreibt (Wörter gleicher Länge können in beliebiger Reihenfolge, möglicherweise mit Wiederholungen, ausgegeben werden.)

45. (0 Punkte) Zeigen Sie:

(a) Die rekursiven Sprachen sind unter Differenz abgeschlossen. (Das heißt: Mit L_{1} und L_{2} ist auch L_{1} − L_{2} immer rekursiv.)

(b) Die rekursiv aufzählbaren Sprachen sind unter Differenz nicht abgeschlossen.

46. (5 Punkte) Bestimmen Sie die Sprache, die von der Grammatik mit dem Startsymbol S, dem Terminalalphabet {a} und den folgenden Regeln erzeugt wird. Begründen Sie Ihre Antwort, indem Sie den Ableitungsprozess in Worten beschreiben.

\begin{matrix}S → ACaB & aD → Da \\ Ca → aaC & AD → AC \\ CB → DB & aE → Ea \\ CB → E & AE → ε \end{matrix}

47. (0 Punkte) Bestimmen Sie kontextsensitive Grammatiken für folgende Sprachen. (a) L_{1} = { ww | w ∈ {0, 1}^{+} } (b) L_{2} = { 0^{i^{2}} | i ≥ 1 }

(c) L_{3} = { 0^{i} | i ≥ 2, i ist keine Primzahl }
(d) L_{4} = { 0^{i}1^{i}2^{i} | i ≥ 1 }

48. (6 Punkte) Geben Sie eine eindeutige kontextfreie Grammatik für arithmetische Ausdrücke über dem Alphabet {+, −, ∗, ÷, ↑, (,), Z} an. Die Grammatik soll die Ausdrücke gemäß den üblichen mathematischen Regeln analysieren, wobei der Operator ↑ für die Exponentiation höchste Priorität hat und rechtsassoziativ ist. Es soll also zum Beispiel Z ↑ Z ↑ Z wie Z ↑ (Z ↑ Z) interpretiert werden, und Z −Z ÷Z ∗Z −Z ∗Z wie (Z −((Z ÷Z)∗Z))−(Z ∗Z).

49. (0 Punkte) Betrachten Sie die kontextfreie Grammatik G mit den Regeln

\begin{matrix}S → ScS | A \\ A → aAb | ε \end{matrix}

(a) Beschreiben Sie die erzeugte Sprache, und zeigen Sie, dass G mehrdeutig ist.

(b) Geben Sie eine eindeutige kontextfreie Grammatik an, die dieselbe Sprache erzeugt.

50. (0 Punkte) Zeigen Sie, dass die Grammatiken

(a) S → SS | (S) | ε

(b) S → (S)S | ε

die gleiche Sprache erzeugen und dass (a) mehrdeutig und (b) eindeutig ist.

51. (0 Punkte) Bringen Sie die Grammatik aus Aufgabe 49 und Ihre Antwort aus Aufgabe 49b in Chomsky-Normalform.

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

Abgabe bis Montag, 2. Juli 2001

52. (a) (0 Punkte) Geben Sie eine kontextfreie Grammatik für arithmetische Ausdrücke über dem Alphabet {+, ∗, (,), Z} an. Dabei sollen nur Ausdrücke ohne überflüssige Klammern erzeugt werden, d. h., solche Audrücke, die nach den üblichen mathematischen Vorrangregeln einen anderen Wert bekommen, wenn man Klammern weglässt. Zum Beispiel sind die Klammern in Z ∗ (Z + Z) notwendig, weil man den Ausdruck ohne Klammern Z ∗ Z + Z als (Z ∗ Z) + Z lesen würden. Aus diesem Grund sind auch die Klammern im Ausdruck (Z ∗ Z) + Z überflüssig (redundant).

(b) (0 Punkte) Lösen Sie die Aufgabe mit dem erweiterten Alphabet {+, −, ∗, ÷, (,), Z}.

53. (0 Punkte) Beweisen Sie, dass man zu jeder kontextsensitiven Grammatik eine äquivalente Grammatik finden kann, deren Regeln von der Gestalt S → ε oder von folgender Gestalt sind.

α_{1}Aα_{2} → α_{1}βα_{2}, mit A ∈ V, α_{1}, α_{2}, β ∈ (T ∪ V − {S})^{∗}, β ≠ ε

54. (6 Punkte) Welche der folgenden Sprachen sind kontextfrei?

(a) (4 Punkte) L_{1} = { 0^{i}1^{i^{2}} | i ≥ 1 }

(b) (2 Punkte) L_{2} = { 0^{i}1^{j} | i ≥ j }

(c) Die Sprache der Doppelwörter L_{3} = { ww | w ∈ {0, 1}^{∗} }

(d) L_{4} = { 0^{i}1^{j}0^{k}1^{l} | i + j = k + l }, L_{5} = { 0^{i}1^{j}0^{k}1^{l} | i + k = j + l }

(e) L_{6} = { w ∈ {0, 1}^{∗} | w enthält doppelt so viele Nullen wie Einsen }

55. (5 Punkte) Beweisen Sie, dass die Grammatik mit den Regeln S → aS | aSbS | ε genau die Wörter über {a, b} erzeugt, in denen jeder Präfix mindestens so viele a’s wie b’s enthält.

56. (0 Punkte) Die Grammatik

S → if (B) S | if (B) S else S | print(0); | print(1); | print(2); B → true | false

ist mehrdeutig, wie das Beispiel

if (true) if (false) if (false) print(0); else if (true) print(0); else print(1); else print(2);

zeigt. Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass eine else-Klausel immer dem letzten if zugeordnet wird, dem noch keine else-Klausel zugeordnet wurde. Nach dieser Regel würde der obige Ausdruck 2 drucken, wenn man ihn als Programm auffasst. (Welche Werte könnte das Programm sonst noch drucken, wenn man alle Mehrdeutigkeiten berücksichtigt?) Geben Sie eine eindeutige Grammatik an, die dieser Regel entspricht.

57. (5 Punkte) Bleibt eine eindeutige Grammatik bei der Transformation in Chomsky-Normal-form eindeutig? Beweisen Sie Ihre Antwort.

58. (0 Punkte) G sei eine Grammatik in Chomsky-Normalform, die eine endliche Sprache erzeugt. Finden Sie eine Schranke für das längste Wort in L(G).

59. (0 Punkte) Wie lang kann die Ableitung eines Wortes w bei einer Grammatik in Chomsky-Normalform höchstens sein?

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

Letztes Pflichtübungsblatt — Abgabe bis Montag, 9. Juli 2001

60. (0 Punkte) Schreiben Sie eine kontextfreie Grammatik für die regulären Ausdrücke über dem Alphabet {0, 1}. Sie können annehmen, dass die Ausdrücke voll geklammert sind, entsprechend der ursprünglichen Definition regulärer Ausdrücke, zum Beispiel

(((0 + (1)^{∗})) · ((0 + (0 · 1)) + ε))

61. (0 Punkte) Kontextfreie Sprachen sind unter Umkehrung (Spiegelung) abgeschlossen.

62. (4 Punkte) Entfernen Sie die überflüssigen Variablen und Regeln aus dieser Grammatik:

\begin{matrix}S → AB | CA & B → BC | AB | BDE & D → ADEba | ACA \\ A → a & C → aB | c & E → DD | BA \end{matrix}

63. (7 Punkte) Überprüfen Sie mit dem CYK-Algorithmus, ob das Wort w = cdccd von der folgenden Grammatik erzeugt wird, und geben Sie gegebenfalls eine Ableitung für w an.

\begin{matrix}S → AB | CD | AS & B → SB | d & D → CD | d \\ A → AS | DC & C → CA | c \end{matrix}

64. (0 Punkte) Übersetzen Sie den folgenden vereinfachten Ausschnitt aus der Syntax der Programmiersprache Java aus der EBNF (extended Backus-Naur-Form) in entsprechende kontextfreie Regeln:

TryBlock ::= try Block Catches | try Block [ Catches ] finally Block Catches ::= CatchClause { CatchClause } CatchClause ::= catch ( Exception Identifier ) Block Exception ::= Identifier

Die Terminalsymbole sind hier fett gedruckt. Sie können die Variablen durch passende einbuchstabige Namen abkürzen. (Wozu dient eigentlich die Variable ”Exception“, die man doch genausogut mit der Regel ”Exception ::= Identifier“ eliminieren könnte?)

65. (0 Punkte) Kann man für eine gegebene kontextfreie Grammatik G und eine gegebene reguläre Sprache L_{1} entscheiden, ob L(G) = L_{1} ist?

66. (5 Punkte) Betrachten Sie die deterministischen Zweiweg-Kellerautomaten mit dem Eingabealphabet Σ = {a}, dem Kelleralphabet Γ = {0, 1, Z_{0}} und der Übergangsfunktion δ: Q × Γ × (Σ ∪ {♢, $}) → Q × Γ^{∗} × {L, N, R}.

δ(q_{0}, γ, a) = (q_{0}, 0γ, R), für γ ∈ Γ.
δ(q_{0}, γ, $) = (q_{1}, γ, N), für γ ∈ Γ.
δ(q_{1}, 1, x) = (q_{1}, ε, L), für x = 0 oder x = $.
δ(q_{1}, 0, x) = (q_{0}, 1, N), für x = 0 oder x = $.
δ(q_{1}, Z_{0}, x) = (q_{1}, ε, N), für x = 0 oder x = $.

Die übrigen Werte von δ (für x = ♢) sind beliebig.

(a) (0 Punkte) Beschreiben Sie das Verhalten des Automaten bei Eingabe des Wortes a^{n}, für n = 0, 1, 2, 3 und für allgemeines n.

(b) (5 Punkte) Bestimmen Sie die Entladefunktion E: Q × {0, …, n + 1} × Γ → Q × {0, …, n + 1} bei Eingabe des Wortes a^{n}.

67. (0 Punkte) Wie kann man zu einem regulären Ausdruck einen regulären Ausdruck für die komplementäre Sprache finden?

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

ergänzende Zusatzübungen zur Wiederholung und Vertiefung freiwillige Abgabe bis Montag, 16. Juli 2001

68. (a) (3 Zusatzpunkte) Beschreiben Sie formal, wie man einen nichtdeterministischen Kellerautomaten, der mit akzeptierenden Zuständen arbeitet, in einen äquivalenten Kellerautmaten umwandelt, der mit leerem Keller akzeptiert.

(b) Beschreiben Sie die Transformation in die umgekehrte Richtung.

(c) Lösen Sie die beiden obigen Aufgaben auch für deterministische Zweiweg-Kellerauto-maten.

69. (6 Zusatzpunkte) Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen gegenüber dem Durchschnitt mit regulären Sprachen sind. (Hinweis: Wählen Sie ein geeignetes Maschinenmodell für die kontextfreien Sprachen und verfahren Sie ähnlich wie bei Aufgabe 19.)

70. Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen gegenüber der Vereinigung mit regulären Sprachen sind.

71. (4 Zusatzpunkte) Konstruieren Sie (a) eine Grammatik, (b) einen Kellerautomaten für die Sprache { ww^{R} | w ∈ {0, 1}^{∗} }.

72. Konstruieren Sie einen deterministischen Kellerautomaten für die Sprache

{ w#w^{R} | w ∈ {−1, 1}^{∗} } .

73. Konstruieren Sie einen deterministischen Kellerautomaten für die Sprache der Wörter, die gleich viele Nullen und Einsen enthalten.

74. Beweisen Sie, dass die Sprachen { a^{i}b^{i}c^{j} | i, j ≥ 0 } und { a^{i}b^{j}c^{j} | i, j ≥ 0 } deterministische kontextfreie Sprachen sind. Zeigen Sie mit Hilfe dieser Sprachen, dass die deterministischen kontextfreien Sprachen nicht gegenüber dem Durchschnit abgeschlossen sind.

75. Beweisen Sie: Wenn eine Sprache von einem deterministischen Kellerautomaten (mit akzeptierenden Zuständen) akzeptiert wird, dann gibt es eine eindeutige kontextfreie Sprache für diese Grammatik.

76. Sind die Sprachen, die von deterministischen Zweiweg-Kellerautomaten akzeptiert werden, abgeschlossen gegenüber Umkehrung (Spiegelbild)?

77. (Schwierig, 5 Zusatzpunkte) Sind die deterministischen kontextfreien Sprachen abgeschlossen gegenüber Umkehrung?

78. (a) Wandeln Sie den folgenden Kellerautomaten in einen äquivalenten Kellerautomaten mit nur einem einzigen Zustand um. δ = {(q_{0}, 0, γ, q_{1}, Z_{0}γ), (q_{0}, 1, γ, q_{1}, Z_{1}γ), (q_{1}, 0, γ, q_{0}, Z_{0}γ), (q_{1}, 1, γ, q_{1}, Z_{1}Z_{1}), (q_{0}, 1, Z_{1}, q_{0}, ε), (q_{0}, 0, Z_{0}, q_{0}, ε)}, wobei γ jeweils für ein beliebiges Kellersymbol γ ∈ Γ = {Z_{0}, Z_{1}} steht.

(b) Konstruieren Sie eine entsprechende kontextfreie Grammatik.

79. Welche Beispiele von Typ-0-Sprachen kennen Sie, die keine Typ-1-Sprachen sind? Welche Beispiele von Typ-1-Sprachen kennen Sie, die keine Typ-2-Sprachen sind? Welche Beispiele von Typ-2-Sprachen kennen Sie, die keine Typ-3-Sprachen sind? Welche Beispiele von kontextfreien Sprachen kennen Sie, die keine deterministischen kontextfreien Sprachen sind?