Grundlagen der theoretischen Informatik, SS 2001

Nachklausur zum 2. Teil, Dienstag, 9. Oktober 2001 — Lösungen

Aufgabe 1 2 3 (4)
Punkte 10 10 10 (5)
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf dem dafür vorgesehenen Blatt. Verwenden Sie gegebenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben. Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Wandeln Sie die folgende Grammatik in Chomsky-Normalform um. Prüfen Sie dann mit dem CYK-Algorithmus nach, dass das Wort aaa+aa+a− von dieser Grammatik erzeugt wird, und geben Sie einen Syntaxbaum und eine Linksableitung (für die umgewandelte Grammatik) an.

\begin{matrix}S → SSS | A \\ A → A+A | AS− | a \end{matrix}

Lösung: Erster Schritt. Trennung von Variablen und Terminalsymbolen:

S → SSS | A,  A → AP A | ASM | a,  P → +,  M → −

Zweiter Schritt. Elimination von zu langen Regeln:

S → ST, T → SS; S → A
A → AB, B → P A; A → AC, C → SM
P → +, M → −, A → a

Dritter Schritt. Elimination der zu kurzen Regel S → A: Sie wird ersetzt durch S → AB, S → AC, S → a.

Eine Linksableitung ist dann S → AC → aC → aSM → aST M → aaT M → aaSSM → aaABSM → aaaBSM → aaaP ASM → aaa+ASM → aaa+aSM → aaa+aaM → aaa+aa−.

2. (10 Punkte) Beweisen Sie, dass die folgenden Sprachen über dem Alphabet {a, b, c} nicht kontextfrei sind.

(a) L_{1} = { w | w enthält gleich viele a’s, b’s und c’s. }

(b) L_{2} = { a^{i}b^{j}c^{k} | 1 ≤ i < j = k } Lösung zu (a): L_{1} ∩ a^{∗}b^{∗}c^{∗} = { a^{i}b^{i}b^{i} | i ≥ 0 } und diese Sprache ist bekanntlich nicht kontextfrei. Beim Schnitt mit einer regulären Sprache bleibt eine kontextfreie Sprache kontextfrei.

Man kann auch das Pumping-Lemma auf a^{N}b^{N}c^{N} ∈ L_{1} anwenden: a^{N}b^{N}c^{N} = uvxyz. Wegen |vxy| ≤ N kann vy nicht a’s, b’s und c’s, enthalten. Daher ist vy ∈ {a, b}^{+} ∪ {b, c}^{+}. Somit enthält uxz nicht gleich viele a’s, b’s und c’s. Widerspruch.

Lösung zu (b): Beweis durch Widerspruch. N sei die Konstante aus dem Pumping-Lemma. Wende das Pumping-Lemma auf a^{N}b^{N+1}c^{N+1} ∈ L_{2} an: Dann ist a^{N}b^{N+1}c^{N+1} = uvxyz mit |vxy| ≤ N und |vy| ≥ 1, und alle Wörter uv^{i}xy^{i}z für i ≥ 0 gehören zu L_{2}.

(a) Wenn v oder y nicht von der Form a^{∗} ∪ b^{∗} ∪ c^{∗} ist, dann wäre uv^{2}xy^{2}z ∉ a^{∗}b^{∗}c^{∗} und somit uv^{2}xy^{2}z ∉ L_{2}.

(b) Wenn y = c^{i} (i ≥ 0) ist, muss v = b^{i} sein, denn sonst hätte uxz nicht gleich viele b’s und c’s. Also ist i ≥ 1. Dann hat aber uxz nicht mehr b’s als a’s und gehört somit nicht zu L_{2}, ein Widerspruch.

(c) Wenn y = b^{i} (i ≥ 1) ist, dann ist v ∈ a^{∗} ∪ b^{∗}, und uv^{2}xy^{2}z enthält mehr b’s als c’s.

(d) Wenn y = a^{i} (i ≥ 1) ist, dann ist auch v ∈ a^{∗}, und uv^{i}xy^{i}z enthält für genügend großes i mehr a’s als b’s.

Damit sind alle Möglichkeiten für y erschöpft.

3. (10 Punkte) Geben Sie für die folgende Grammatik einen äquivalenten Kellerautomaten an. (Entscheiden Sie selbst, wie der Automat akzeptieren soll.)

\begin{matrix}S → S − A | A ∗ A \\ A → A − A | a \end{matrix}

Lösung: ”Mechanische“ Übersetzung der Grammatik. Q = {q_{0}}, Γ = {S, A, ∗, −, a}, Σ = {a, ∗, −}, Z_{0} = S. Es gibt nur einen einzigen Zustand q_{0}; deshalb werden im Folgenden bei δ ⊆ Q × Γ × Σ × Q × Γ^{∗} die Zustände nicht geschrieben.

δ = {(S, ε, A − S), (S, ε, A ∗ A), (A, ε, A − A), (−, −, ε), (∗, ∗, ε), (A, a, ε)}.

(Achtung auf die Reihenfolge bei der ersten Regel.) Der Automat akzeptiert mit leerem Keller.

Man kann auch zur größeren Klarheit eigene Kellersymbole für ∗ und − einführen, dann ist

δ = {(S, ε, AMS), (S, ε, AT A), (A, ε, AMA), (M, −, ε), (T, ∗, ε), (A, a, ε)}.

Andere (ursprünglich nicht vorgesehene) Lösungsmöglichkeit: Die Grammatik erzeugt die reguläre Sprache L = a(−a)^{∗}∗a(−a)^{∗}. Der Kellerautomat kann einen endlichen Automaten für diese Sprache simulieren.

4. (Zusatzfrage, 5 Punkte) Ist die Sprache

L = { 0^{i}1^{j}0^{k}1^{l} | i + l = j + k }

kontextfrei? Ist sie regulär? Beweisen Sie Ihre Antworten. Lösung: 1. Sie ist kontextfrei. Man kann L = L_{1} ∪ L_{2} schreiben mit

L_{1} = { 0^{i}1^{j}0^{k}1^{l} | i + l = j + k, i ≤ j }, L_{2} = { 0^{i}1^{j}0^{k}1^{l} | i + l = j + k, l ≤ k }

L_{1} kann man mit m = i − j so schreiben:

L_{1} = { 0^{i}1^{i}1^{m}0^{k}1^{l} | i ≥ 0, m + k = l } = { 0^{i}1^{i} | i ≥ 0 } · { 1^{m}0^{k}1^{m+k} | m, k ≥ 0 },

und analog für L_{2}. Diese Sprachen lassen sich einfach durch kontextfreie Grammatiken erzeugen. Die folgende Grammatik erzeugt L.

S → NA | AN
N → 0N1 | ε  (N erzeugt { 0^{i}1^{i} }.)
A → 1A1 | N  (A erzeugt { 1^{i}0^{j}1^{i+j} }.)
B → 0B0 | N  (B erzeugt { 0^{i+j}1^{i}0^{j} }.)

Ein anderer Beweis konstruiert einen (nichtdeterministischen) Kellerautomaten, der die Differenz zwischen den Häufigkeiten der Symbole zählt. Der Automat durchläuft 4 Phasen:

Phase 1 (Zustand q_{0}): Jede 0 wird als +1 gezählt. Phase 2 (Zustand q_{1}): Jede 1 wird als −1 gezählt. Phase 3 (Zustand q_{2}): Jede 0 wird als −1 gezählt. Phase 4 (Zustand q_{3}): Jede 1 wird als +1 gezählt.

Der Automat akzeptiert, wenn der Zähler am Ende 0 ist. Ein Zähler kann durch eine Folge von +-Symbolen (für positive Werte) oder −-Symbolen (für negative Werte) auf dem Keller dargestellt werden. Ein ”leerer“ Keller entspricht dem Wert 0. Der Übergang von einer Phase zur nächsten ist nichtdeterministisch, weil j = 0 oder k = 0 nicht ausgeschlossen ist. Der folgende Automat akzeptiert L durch leeren Keller: Q = {q_{0}, q_{1}, q_{2}, q_{3}}, Γ = {Z_{0}, +, −}, und

δ = { (q_{0}, γ, 0, q_{0}, +γ), (q_{0}, γ, ε, q_{1}, γ),
(q_{1}, +, 1, q_{1}, ε), (q_{1}, γ^{−}, 1, q_{1}, −γ^{−}), (q_{1}, γ, ε, q_{2}, γ),
(q_{2}, +, 0, q_{2}, ε), (q_{2}, γ^{−}, 0, q_{2}, −γ^{−}), (q_{2}, γ, ε, q_{3}, γ),
(q_{3}, −, 1, q_{3}, ε); (q_{3}, Z_{0}, ε, q_{3}, ε) },

für γ ∈ Γ und γ^{−} ∈ {Z_{0}, −}.

2. Die Sprache L ist nicht regulär. Zum Beispiel ist L ∩ 010^{+}1^{+} = { 010^{i}1^{i} | i ≥ 1 }, und diese Sprache ist nicht regulär, ahnlich wie die bekannte nichtreguläre Sprache { 0^{i}1^{i} | i ≥ 1 }. (Vergleiche auch Aufgabe 4 der ersten Nachklausur zum ersten Teil.) Man kann auch das Pumping-Lemma direkt anwenden.