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

Abgabe bis Montag, 2. Juli 2001

52. (a) (0 Punkte) Geben Sie eine kontextfreie Grammatik für arithmetische Ausdrücke über dem Alphabet {+, ∗, (,), Z} an. Dabei sollen nur Ausdrücke ohne überflüssige Klammern erzeugt werden, d. h., solche Audrücke, die nach den üblichen mathematischen Vorrangregeln einen anderen Wert bekommen, wenn man Klammern weglässt. Zum Beispiel sind die Klammern in Z ∗ (Z + Z) notwendig, weil man den Ausdruck ohne Klammern Z ∗ Z + Z als (Z ∗ Z) + Z lesen würden. Aus diesem Grund sind auch die Klammern im Ausdruck (Z ∗ Z) + Z überflüssig (redundant).

(b) (0 Punkte) Lösen Sie die Aufgabe mit dem erweiterten Alphabet {+, −, ∗, ÷, (,), Z}.

53. (0 Punkte) Beweisen Sie, dass man zu jeder kontextsensitiven Grammatik eine äquivalente Grammatik finden kann, deren Regeln von der Gestalt S → ε oder von folgender Gestalt sind.

α_{1}Aα_{2} → α_{1}βα_{2}, mit A ∈ V, α_{1}, α_{2}, β ∈ (T ∪ V − {S})^{∗}, β ≠ ε

54. (6 Punkte) Welche der folgenden Sprachen sind kontextfrei?

(a) (4 Punkte) L_{1} = { 0^{i}1^{i^{2}} | i ≥ 1 }

(b) (2 Punkte) L_{2} = { 0^{i}1^{j} | i ≥ j }

(c) Die Sprache der Doppelwörter L_{3} = { ww | w ∈ {0, 1}^{∗} }

(d) L_{4} = { 0^{i}1^{j}0^{k}1^{l} | i + j = k + l }, L_{5} = { 0^{i}1^{j}0^{k}1^{l} | i + k = j + l }

(e) L_{6} = { w ∈ {0, 1}^{∗} | w enthält doppelt so viele Nullen wie Einsen }

55. (5 Punkte) Beweisen Sie, dass die Grammatik mit den Regeln S → aS | aSbS | ε genau die Wörter über {a, b} erzeugt, in denen jeder Präfix mindestens so viele a’s wie b’s enthält.

56. (0 Punkte) Die Grammatik

S → if (B) S | if (B) S else S | print(0); | print(1); | print(2); B → true | false

ist mehrdeutig, wie das Beispiel

if (true) if (false) if (false) print(0); else if (true) print(0); else print(1); else print(2);

zeigt. Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass eine else-Klausel immer dem letzten if zugeordnet wird, dem noch keine else-Klausel zugeordnet wurde. Nach dieser Regel würde der obige Ausdruck 2 drucken, wenn man ihn als Programm auffasst. (Welche Werte könnte das Programm sonst noch drucken, wenn man alle Mehrdeutigkeiten berücksichtigt?) Geben Sie eine eindeutige Grammatik an, die dieser Regel entspricht.

57. (5 Punkte) Bleibt eine eindeutige Grammatik bei der Transformation in Chomsky-Normal-form eindeutig? Beweisen Sie Ihre Antwort.

58. (0 Punkte) 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).

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