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

Abgabe bis Montag, 30. Mai 2005, 10:15 Uhr

42. Welche der beiden folgenden Aussagen sind wahr? Beweisen oder widerlegen Sie sie. (a) Wenn L_{1} und L_{2} entscheidbar sind, dann ist auch L_{1}L_{2} entscheidbar.

(b) Wenn L_{1} und L_{2} rekursiv aufzählbar sind, dann ist auch L_{1}L_{2} rekursiv aufzähl-

bar.

43. (10 Punkte) D = { w_{i} | M_{i} akzeptiert w_{i} nicht } bezeichnet die Diagonalsprache und D̄ ihr Komplement.

(a) Zeigen Sie, dass die Sprache D̄ rekursiv aufzählbar ist.

(b) Zeigen Sie, dass die Sprache 0D ∪ 1D̄ nicht rekursiv aufzählbar ist.

44. (2 Zusatzpunkte) Eine andere Konstruktion einer unentscheidbaren Sprache.

U′ := { ⟨M⟩w | M akzeptiert das Wort ⟨M⟩w nicht }

(Der Beweis geht ähnlich wie bei der Diagonalsprache D.)

45. Welche der folgenden Sprachen sind rekursiv, welche sind rekursiv aufzählbar? (a) L_{1} = { 0^{k}⟨M⟩w | M akzeptiert w nach höchstens k Schritten. }

(b) L_{2} = { 0^{k}⟨M⟩w | M hat w nach k Schritten noch nicht akzeptiert. }

(c) L_{3} = Σ^{∗} − (L_{1} ∪ L_{2})

(d) L_{4} = { 0^{k}⟨M⟩w | M akzeptiert w nach mehr als k Schritten. }

46. Beweisen Sie, dass die Sprache L = { 0^{i} | i ≥ 0, das Teilwort 0^{i}123 kommt in der Dezimaldarstellung von π unendlich oft vor } entscheidbar ist. (Sie müssen dazu nichts über π wissen, nur logisch überlegen können. Wie kann L aussehen?)

47. Welche der folgenden Aussagen sind wahr, und welche sind falsch? Welche Aussagen sind trivial, und welche sind absurd?

(a) Jede Teilmenge einer rekursiven Sprache ist rekursiv.

(b) Jede Teilmenge einer rekursiv aufzählbaren Sprache ist rekursiv aufzählbar.

(c) Die Vereinigung zweier entscheidbarer Sprachen ist entscheidbar.

(d) Die Vereinigung zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.

(e) Die Schnittmenge zweier entscheidbarer Sprachen ist entscheidbar.

(f) Die Schnittmenge zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.

(g) Die Schnittmenge einer rekursiv aufzählbaren Sprache und einer entscheidbaren Sprache ist rekursiv aufzählbar.

(h) Jede reguläre Sprache ist rekursiv aufzählbar.

(i) Jede Teilmenge einer regulären Sprache ist regulär.

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