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?