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

Abgabe bis Montag, 18. Juni 2001

36. (6 Punkte) Beweisen Sie:

(a) (6 Punkte) 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ählbar.

37. (0 Punkte) Eine Sprache L ist genau dann entscheidbar, wenn sowohl die Sprache L als auch ihr Komplement L̄ rekursiv aufzählbar ist.

38. (0 Punkte)

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

(b) Zeigen Sie, dass die Sprache 0D ∪ 1D̄ nicht rekursiv aufzählbar ist. (D = { w_{i} | M_{i} akzeptiert w_{i} nicht } ist die Diagonalsprache und D̄ ihr Komplement.)

39. (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.)

40. (6 Punkte) Welche der folgenden Sprachen sind rekursiv, welche sind rekursiv aufzählbar? (a) (3 Punkte) 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) (3 Punkte) L_{4} = { 0^{k}⟨M⟩w | M akzeptiert w nach mehr als k Schritten. }

41. (4 Punkte) Beiweisen 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?)

42. (0 Punkte) 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) Jede reguläre Sprache ist rekursiv aufzählbar.

(d) Jede Teilmenge einer regulären Sprache ist regulär. Weil noch etwas Platz ist, seien hier noch einmal die Kriterien für die Erlangung eines Übungsscheines in Erinnerung gerufen.^{1}

1. 60 % der Gesamtpunktezahl der Übungen. (Die Übungszettel können in Dreiergruppen oder in Zweiergruppen abgegeben werden.)

2. Bei jedem Übungszettel bis auf einen müssen mindestens 30 % der Punkte erreicht werden.

3. 50 % der Punkte bei der Zwischenklausur und 50 % der Punkte bei der Abschlussklausur (oder bei der entsprechenden Nachklausur).

4. Aktive Teilnahme an den wöchentlichen Tutorien und einmaliges Vorrechnen Der Schein wird benotet. Die Note ergibt sich aus den Klausuren.

1http://www.inf.fu-berlin.de/~rote/Lere/Grundlagen%20der%20theoretischen%20Informatik/scheinkrit.html