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

Letztes Pflichtübungsblatt — Abgabe bis Montag, 9. Juli 2001

60. (0 Punkte) 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)) + ε))

61. (0 Punkte) Kontextfreie Sprachen sind unter Umkehrung (Spiegelung) abgeschlossen.

62. (4 Punkte) Entfernen Sie die überflüssigen 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}

63. (7 Punkte) Ü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}

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

65. (0 Punkte) Kann man für eine gegebene kontextfreie Grammatik G und eine gegebene reguläre Sprache L_{1} entscheiden, ob L(G) = L_{1} ist?

66. (5 Punkte) 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}, 1, x) = (q_{1}, ε, L), für x = 0 oder x = $.
δ(q_{1}, 0, x) = (q_{0}, 1, N), für x = 0 oder x = $.
δ(q_{1}, Z_{0}, x) = (q_{1}, ε, N), für x = 0 oder x = $.

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

(a) (0 Punkte) 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) (5 Punkte) Bestimmen Sie die Entladefunktion E: Q × {0, …, n + 1} × Γ → Q × {0, …, n + 1} bei Eingabe des Wortes a^{n}.

67. (0 Punkte) Wie kann man zu einem regulären Ausdruck einen regulären Ausdruck für die komplementäre Sprache finden?