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

Abgabe bis Montag, 25. Juni 2001

44. (5 Punkte) Beweisen Sie:

(a) (0 Punkte) Wenn es eine Turingmaschine gibt, die die Wörter einer Sprache in beliebiger Reihenfolge, möglicherweise mit Wiederholungen, auf ein Ausgabeband schreibt, dann ist diese Sprache rekursiv aufzählbar.

(b) (5 Punkte) Eine Sprache ist genau dann rekursiv, wenn es eine Turingmaschine gibt, die die Wörter der Sprache der Länge nach sortiert auf ein Ausgabeband schreibt (Wörter gleicher Länge können in beliebiger Reihenfolge, möglicherweise mit Wiederholungen, ausgegeben werden.)

45. (0 Punkte) Zeigen Sie:

(a) Die rekursiven Sprachen sind unter Differenz abgeschlossen. (Das heißt: Mit L_{1} und L_{2} ist auch L_{1} − L_{2} immer rekursiv.)

(b) Die rekursiv aufzählbaren Sprachen sind unter Differenz nicht abgeschlossen.

46. (5 Punkte) Bestimmen Sie die Sprache, die von der Grammatik mit dem Startsymbol S, dem Terminalalphabet {a} und den folgenden Regeln erzeugt wird. Begründen Sie Ihre Antwort, indem Sie den Ableitungsprozess in Worten beschreiben.

\begin{matrix}S → ACaB & aD → Da \\ Ca → aaC & AD → AC \\ CB → DB & aE → Ea \\ CB → E & AE → ε \end{matrix}

47. (0 Punkte) Bestimmen Sie kontextsensitive Grammatiken für folgende Sprachen. (a) L_{1} = { ww | w ∈ {0, 1}^{+} } (b) L_{2} = { 0^{i^{2}} | i ≥ 1 }

(c) L_{3} = { 0^{i} | i ≥ 2, i ist keine Primzahl }
(d) L_{4} = { 0^{i}1^{i}2^{i} | i ≥ 1 }

48. (6 Punkte) Geben Sie eine eindeutige kontextfreie Grammatik für arithmetische Ausdrücke über dem Alphabet {+, −, ∗, ÷, ↑, (,), Z} an. Die Grammatik soll die Ausdrücke gemäß den üblichen mathematischen Regeln analysieren, wobei der Operator ↑ für die Exponentiation höchste Priorität hat und rechtsassoziativ ist. Es soll also zum Beispiel Z ↑ Z ↑ Z wie Z ↑ (Z ↑ Z) interpretiert werden, und Z −Z ÷Z ∗Z −Z ∗Z wie (Z −((Z ÷Z)∗Z))−(Z ∗Z).

49. (0 Punkte) Betrachten Sie die kontextfreie Grammatik G mit den Regeln

\begin{matrix}S → ScS | A \\ A → aAb | ε \end{matrix}

(a) Beschreiben Sie die erzeugte Sprache, und zeigen Sie, dass G mehrdeutig ist.

(b) Geben Sie eine eindeutige kontextfreie Grammatik an, die dieselbe Sprache erzeugt.

50. (0 Punkte) Zeigen Sie, dass die Grammatiken

(a) S → SS | (S) | ε

(b) S → (S)S | ε

die gleiche Sprache erzeugen und dass (a) mehrdeutig und (b) eindeutig ist.

51. (0 Punkte) Bringen Sie die Grammatik aus Aufgabe 49 und Ihre Antwort aus Aufgabe 49b in Chomsky-Normalform.