Grundlagen der theoretischen Informatik, SS 2001

2. Klausur, Mittwoch, 11. Juli 2001 — Lösungen

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) L_{1} sei eine kontextfreie Sprache über dem Alphabet {0, 1}, und

L_{2} = { w_{1}0w_{2}0 … w_{n}0 | w_{1}w_{2} … w_{n} ∈ L_{1}, n ≥ 0 }

sei die Sprache, wo nach jedem Buchstaben jedes Wortes eine Null eingefügt ist. Beweisen Sie, dass L_{2} ebenfalls kontextfrei ist.

Lösung: G_{1} sei eine Grammatik, die L_{1} erzeugt. Ersetze auf der rechten Seite aller Regeln 0 durch 00 und 1 durch 10. Die entstehende Grammatik erzeugt L_{2}.

Alternativlösung: K_{1} sei ein Kellerautomat, der L_{1} akzeptiert. Für jeden Übergang (q, a, γ, q′, γ′) ∈ δ_{1} mit a ∈ Σ erzeugen wir zwei Übergänge (q, a, γ, q_{i}, γ) und (q_{i}, 0, γ, q′, γ′) in δ_{2}, wobei q_{i} jedesmal ein neuer Zustand ist, der sonst nirgends vorkommt. Die Übergänge (q, ε, γ, q′, γ′) ∈ δ_{1} übernehmen wir unverändert in δ_{2}.

Nach jedem Buchstaben des Eingabewortes muss somit eine 0 gelesen werden, dass der Automat weiterarbeiten kann. Der neue Kellerautomat akzeptiert L_{2}.

2. (10 Punkte) Konstruieren Sie eine kontextfreie Grammatik für die Sprache der Wörter über {0, 1}, die kein Palindrom sind:

L = { w | w ≠ w^{R} }

Lösung: \begin{matrix}S → 0S0 | 1S1 | 0T 1 | 1T 0 \\ T → 0T | 1T | ε \end{matrix}

Jedes Wort w ∈ L muss Länge |w| ≥ 2 haben, ist also von der Form w = aw′b mit a, b ∈ {0, 1}. Wenn a ≠ b, dann kann w′ ∈ {0, 1}^{∗} beliebig sein. Die Sprache {0, 1}^{∗} wird vom Symbol T erzeugt. Wenn a = b ist, dann darf w′ kein Palindrom sein. Es ist also w′ ∈ L (S → w′).

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

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

Lösung: Erster Schritt. Separation der Terminalsymbole von den Variablen.

S → SMA | AP A,  A → AMA | a,  M → −,  P → ∗

Zweiter Schritt. Zu lange Regeln werden in eine Kette von Regeln aufgespalten.

\begin{matrix}S → SS_{1}, & S_{1} → MA & A → AA_{1}, A_{1} → MA \\ S → AS_{2}, & S_{2} → P A & A → a,  M → −,  P → ∗ \end{matrix}

Dritter Schritt: Regeln der Form A → ε werden eliminiert, und es wird sichergestellt, dass S nicht auf der rechten Seite einer Regel vorkommt. Da wir keine solchen Regeln haben, ist dieser Schritt nicht notwendig. Wenn man trotzdem S nicht auf der rechten Seite einer Regel haben möchte, kann man eine neue Startvariable S_{0} einführen und dann die Regel S_{0} → S eliminieren. Das würde auf die folgende Grammatik führen:

S_{0} → SS_{1} | AS_{2}

S → SS_{1}, S_{1} → MA  A → AA_{1}, A_{1} → MA
S → AS_{2}, S_{2} → P A  A → a,  M → −,  P → ∗

Vierter Schritt: Elimination der zu kurzen Regeln der Form A → B. Da keine solchen Regeln vorkommen, entfällt dieser Schritt.

Ausführen des CYK-Algorithmus:

a  ∗  a  −  a  −  a ; A  P  A M  A M  A ; ∅  \underline{S_{2}}  ∅ S_{1}, A_{1} ∅ S_{1}, \underline{A_{1}} ; \underline{S}  ∅  A  ∅  \underline{A} ; ∅  S_{2}  ∅ \underline{S_{1}}, A_{1} ; S  ∅  A ; ∅  S_{2} ; \underline{S}  \begin{aligned}& S \\ \begin{aligned}& S \\ \begin{matrix}A \\ a \end{matrix} & \begin{aligned}& S_{2} \\ \begin{matrix}P \\ ∗ \end{matrix} & & \begin{matrix}A \\ a \end{matrix} \end{aligned} \end{aligned} & \begin{aligned}& S_{1} \\ \begin{matrix}M \\ − \end{matrix} & \begin{aligned}& A \\ \begin{matrix}A \\ a \end{matrix} & \begin{matrix}A_{1} \\ \begin{matrix}M \\ − \end{matrix} & \begin{matrix}A \\ a \end{matrix} \end{matrix} \end{aligned} \end{aligned} \end{aligned}

Das Symbol S erscheint im untersten Element. Daher wird das Wort von der Grammatik erzeugt. Es gibt mehrere Möglichkeiten, die Entstehung des Startsymbols zurückzuverfolgen. Wenn man zum Beispiel die Einträge auswählt, die in der Tabelle unterstrichen sind, erhält man Ableitungsbaum auf der rechten Seite. Er entspricht der folgenden Linksableitung. (Es gibt noch vier andere Ableitungsbäume.)

S → SS_{1} → AS_{2}S_{1} → aS_{2}S_{1} → aP AS_{1} → a∗AS_{1} → a∗aS_{1} → a∗aMA → → a∗a−A → a∗a−AA_{1} → a∗a−aA_{1} → a∗a−aMA → a∗a−a−A → a∗a−a−a

4. (Zusatzfrage, 5 Punkte) Ist das Komplement Ū der universellen Sprache,

Ū = { ⟨M⟩w | M akzeptiert w nicht }

entscheidbar? Beweisen Sie Ihre Antwort. Lösung: Eine Sprache ist genau dann entscheidbar, wenn ihr Komplement entscheidbar ist. Da die universelle Sprache U nicht entscheidbar ist, ist auch Ū nicht entscheidbar.