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

Abgabe bis Montag, 27. Juni 2005, 10:15 Uhr

64. (a) 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.

(b) Lösen Sie die gleiche Aufgabe für die Sprache

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

wo nach jedem Buchstaben abwechselnd eine Null und eine Eins eingefügt wird.

65. Wenn man beim Beweis des Pumpinglemmas den längsten Pfad im Ableitungsbaum betrachtet, kann man die stärkere Aussage herleiten, dass es eine Zerlegung w = xyzuv mit der Längenbeschränkung |yzu| ≤ n_{0} gibt, sodass all Wörter xy^{i}zu^{i}v ∈ L sind.

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

(a) L′_{1} = { w | w enthält doppelt so viele a’s wie b’s und doppelt so viele b’s wie c’s } (b) L_{2} = { a^{i}b^{j}c^{k} | i > j ≥ k ≥ 1 }

67. 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)) + ε))

68. Kontextfreie Sprachen sind unter Umkehrung (Spiegelung) abgeschlossen.

69. Entfernen Sie überflüssige 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}

70. (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 zusammen mit der Regel ”Exception ::= Identifier“ eliminieren könnte?)

71. (a) Bleibt eine eindeutige Grammatik bei der Transformation in Chomsky-Normal-

form eindeutig?

(b) 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).

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