Blatt 11

Humboldt-Universität zu Berlin
Prof. Dr. Klaus Reinhardt
Einführung in die Theoretische Informatik
5. Januar 2015
Übungsblatt 11
Besprechung der mündlichen Aufgaben am 12.–15. 1. 2015
Abgabe der schriftlichen Lösungen bis 15:10 am 19. 1. 2015
Aufgabe 90 Zeigen Sie:
6 Punkte
(a) Es gibt eine Sprache A mit A∗ ∈ REG, aber A ∩ {1}∗ ∉ REC.
(mündlich)
(b) Die Reduktionsrelation ≤ ist reflexiv und transitiv, aber nicht antisymmetrisch
(und somit keine Ordnung).
(mündlich)
(c) Die Klasse RE ist unter ≤ abgeschlossen.
(mündlich)
(d) Es existiert eine DTM M mit M (w#x) = Mw (x) für jede Eingabe der Form
∗
w#x wobei w, x ∈ {0, 1} (d.h. M simuliert Mw bei Eingabe x).
(mündlich)
(e) Das spezielle Halteproblem K ist RE-vollständig.
(mündlich)
∗
(f) Die Sprache {w#x#y ∣ w, x, y ∈ {0, 1} und Mw ist eine DTM mit Mw (x) = y}
ist RE-vollständig.
(3 Punkte)
(g) Für zwei Sprachen A, B gilt A ≤ B genau dann, wenn A ≤ B.
(mündlich)
(h) Eine Sprache A ist genau dann RE-vollständig, wenn ihr Komplement A co-REvollständig ist.
(mündlich)
(mündlich)
(i) Jede Sprache L ∈ RE mit L ≤ L ist entscheidbar.
(j) Es gibt keine RE-vollständige Sprache, die co-RE-vollständig ist.
(3 Punkte)
Aufgabe 91 Es sei Eq = {v#u ∣ L(Mv ) = L(Mu )}. Zeigen Sie:
(a) Das Halteproblem lässt sich auf Eq reduzieren.
(b) Das Halteproblem lässt sich auf Eq reduzieren.
(c) Weder Eq noch Eq sind semi-entscheidbar.
Aufgabe 92
Für eine Sprachklasse S sei
5 Punkte
(mündlich)
(3 Punkte)
(2 Punkte)
mündlich, optional
LS = {w ∈ {0, 1} ∣ L(Mw ) ∈ S} .
∗
Beweisen sie folgende Variante des Satzes von Rice:
LS ist unentscheidbar, außer wenn LS ∈ {∅, {0, 1} } ist.
∗
Aufgabe 93
11 Punkte
Bestimmen Sie, welche der folgenden Sprachen entscheidbar, semi-entscheidbar, oder
nicht semi-entscheidbar sind. Begründen Sie.
∗
(a) L1 = {w ∈ {0, 1} ∣ Mw (w) führt immer die Kopfbewegung R aus} (mündlich)
(b) L2 = {w ∈ {0, 1} ∣ Mw (w) führt nie die Kopfbewegung N aus}
(mündlich)
(c) L3 = {w ∈ {0, 1} ∣ es gibt ein w ∈ {0, 1} mit Mw (w ) = 0}
∗
∗
(d) L4 = {w ∈ {0, 1} ∣ es gibt ein w′ ∈ {0, 1} mit Mw′ (w) = 0}
∗
(e) L5 = {w ∈ {0, 1} ∣ L(Mw ) ∈ REG}
(mündlich)
(mündlich)
(mündlich)
(f) L6 = {w ∈ {0, 1} ∣ L(Mw ) ist rekursiv aufzählbar}
∗
(g) L7 = {w ∈ {0, 1} ∣ es gibt ein w′ ≠ w mit L(Mw ) = L(Mw′ )}
∗
(h) L8 = {w ∈ {0, 1} ∣ Mw (w) besucht kein Bandfeld mehrmals}
(2 Punkte)
(2 Punkte)
(2 Punkte)
(i) L9 = {w ∈ {0, 1} ∣ Mw (w) = w}
(2 Punkte)
(j) L10 = {w ∈ {0, 1} ∣ L(Mw ) ist semi-entscheidbar}
(3 Punkte)
∗
∗
′
∗
′
∗
∗
∗
mündlich
Aufgabe 94
(a) Entscheiden Sie die beiden folgenden PCP-Instanzen:
a
I1 = (
ab
ba
ab
abb bab
)
bb abb
I2 = (
aaaa
aa
)
aaa aaaaa
Geben Sie im positiven Fall eine PCP-Lösung an und beweisen Sie im negativen
Fall, dass keine PCP-Lösung existiert.
(b) Reduzieren Sie PCP auf MPCP.
(c) Ist PCP≤k , die Einschränkung von PCP auf Instanzen mit höchstens k Wortpaaren, für jedes k ≥ 1 entscheidbar? Begründen Sie.
(optional)
Aufgabe 95
8+2 Punkte
Betrachten Sie die Grammatik G = ({A, B, C}, {a, b} , P, A) mit folgenden Regeln:
P ∶ A → BabC (1)
Ba → Cba, aBa (2, 3)
bC → bCb (4)
C → ab (5)
(a) Geben Sie eine Ableitung für das Wort v = aabbababb in G an.
(2 Punkte)
(b) Sei Γ = {A, B, C, a, b, ⟨, ∣, ⟩} und sei f die in der Vorlesung definierte Funktion,
∗
die L(G) auf MPCPΓ reduziert. Geben Sie für ein beliebiges Wort w ∈ {a, b}
explizit die zugehörige MPCPΓ -Instanz f (w) an.
(4 Punkte)
(c) Bestimmen Sie eine MPCPΓ -Lösung α der Länge
• höchstens 23,
• höchstens 22,
• 21,
für f (v) und das entsprechende Lösungswort.
(2 Punkte)
(1 Zusatzpunkt)
(1 Zusatzpunkt)

Download Report