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

freiwillige Abgabe bis Montag, 11. Juli 2005, 10:15 Uhr

79. (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}, ε)}. Dabei steht γ jeweils für ein beliebiges Kellersymbol γ ∈ Γ = {Z_{0}, Z_{1}}.

(b) Konstruieren Sie eine entsprechende kontextfreie Grammatik.

80. Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen gegenüber der Vereinigung mit regulären Sprachen sind.

81. (a) Erweitern Sie das Haskell-Programm aus der Vorlesung zur Simulation eines deterministischen Zweiweg-Kellerautomaten und zur Berechnung der Entladefunktion^{1} so, dass es die Anzahl der Schritte ausgibt, die der Automat bis zum Leeren des Kellers macht.

(b) Erweitern Sie das Programm so, dass es auch dann terminiert, wenn der Automat in eine unendliche Schleife gerät.^{2}

82. Betrachten Sie die deterministischen Zweiweg-Kellerautomaten mit dem Eingabealphabet Σ = {a}, dem Kelleralphabet Γ = {0, 1, Z_{0}} und der Übergangsfunktion δ: Q×(Σ∪ {%, $}) × Γ → Q × Γ^{∗} × {L, N, R}.

δ(q_{0}, a, γ) = (q_{0}, 0γ, R), für γ ∈ Γ. δ(q_{0}, $, γ) = (q_{1}, γ, N), für γ ∈ Γ. δ(q_{1}, x, 1) = (q_{1}, ε, L), für x = 0 oder x = $. δ(q_{1}, x, 0) = (q_{0}, 1, N), für x = 0 oder x = $. δ(q_{1}, x, Z_{0}) = (q_{1}, ε, N), für x = 0 oder x = $.

Die übrigen Werte von δ (für x = %) sind beliebig.

(a) Beschreiben Sie das Verhalten des Automaten bei Eingabe des Wortes a^{n}, für n = 0, 1, 2, 3 und für allgemeines n.

(b) Bestimmen Sie die Entladefunktion E: Q × {0, …, n + 1} × Γ → Q × {0, …, n + 1} bei Eingabe des Wortes a^{n}.

83. (a) Beschreiben Sie formal, wie man einen nichtdeterministischen Zweiweg-Kellerauto-maten, der mit akzeptierenden Zuständen arbeitet, in einen äquivalenten Zweiweg-Kellerautomaten umwandelt, der mit leerem Keller akzeptiert.

(b) Beschreiben Sie die Transformation in die umgekehrte Richtung.

84. Mit deterministischen Zweiweg-Kellerautomaten kann man alle deterministisch kontextfreien Sprachen akzeptieren.

85. (4 Zusatzpunkte) Konstruieren Sie (a) eine Grammatik, (b) einen Kellerautomaten für die Sprache { ww^{R} | w ∈ {0, 1}^{∗} }.

86. 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.

87. Sind die Sprachen, die von deterministischen Zweiweg-Kellerautomaten akzeptiert werden, abgeschlossen gegenüber Umkehrung (Spiegelbild)?

1http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Teilwort.hs 2http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Zaehler.hs