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

Abgabe bis Montag, 4. Juli 2005, 10:15 Uhr

72. (a) Zeigen Sie, dass die Sprache

L_{1} = { w ∈ {a, b}^{∗} | w enthält gleich viele a’s wie b’s }

deterministisch kontextfrei ist.

(b) Geben Sie eine kontextfreie Grammatik für die Sprache L_{1} an.

(c) Geben Sie eine kontextfreie Grammatik für die Sprache

L_{2} = { w | w enthält doppelt so viele a’s wie b’s }

über dem Alphabet Σ = {a, b} an.

(d) Lösen Sie dieselbe Aufgabe über dem Alphabet {a, b, c}.

73. (a) Schreiben Sie eine kontextfreie Grammatik für die durch den regulären Aus-

druck

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

definierte Sprache.

(b) Wie kann man allgemein für einen regulären Ausdruck eine entsprechende kontextfreie Grammatik erzeugen?

74. (a) (6 Punkte) Wie kann man entscheiden, ob eine kontextfreie Grammatik eine

endliche Sprache erzeugt?

(b) (4 Punkte) Kann man für eine gegebene kontextfreie Grammatik G und eine durch einen endlichen Automaten gegebene reguläre Sprache L_{1} entscheiden, ob L(G) = L_{1} ist?

(c) (0 Punkte) Wie kann man für eine gegebene kontextfreie Grammatik G und eine durch einen endlichen Automaten gegebene reguläre Sprache L_{1} entscheiden, ob L(G) ⊆ L_{1} ist? (Hier müssen Sie mehrere bekannte Ergebnisse kombinieren.)

75. Das Post’sche Korrespondenzproblem und kontextfreie Sprachen.

(a) Für gegebene x_{1}, …, x_{k} ∈ Σ^{∗} ist die Sprache { a_{i_{n}}a_{i_{n−1}} … a_{i_{1}}x_{i_{1}}x_{i_{2}} … x_{i_{n}} | n ≥ 1, 1 ≤ i_{j} ≤ k } kontextfrei, wobei a_{1}, a_{2}, …, a_{k} neue Buchstaben sind, die nicht zu Σ gehören. (Versuchen Sie, mit möglichst wenigen Regeln auszukommen.)

(b) Zu jedem Post’schen Korrespondenzproblem kann man zwei kontextfreie Grammatiken G_{1} und G_{2} konstruieren, sodass das Post’schen Korrespondenzproblem genau dann eine Lösung hat, wenn L(G_{1}) ∩ L(G_{2}) ≠ ∅. Was folgt daraus für das entsprechende Entscheidungsproblem für kontextfreie Grammatiken?

76. Ü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}

77. Zeigen Sie, dass die Chomsky-Hierarchie echt ist: Geben Sie eine Typ-0-Sprache an, die keine Typ-1-Sprache ist. Geben Sie eine Typ-1-Sprache an, die keine Typ-2-Sprache ist. Geben Sie eine Typ-2-Sprache an, die keine Typ-3-Sprache ist. (Und geben Sie eine Sprache an, die keine Typ-0-Sprache ist.)

78. Beschrieben Sie, wie man zu einem regulären Ausdruck einen regulären Ausdruck für die komplementäre Sprache findet.