Heimübung 4

Christian Scheideler
u. v. a.
Paderborn, 07.11.2014
Abgabe 17.11.2014, 13.45 Uhr
K¨asten im D3-Flur
Heimu
¨bung zur Vorlesung
Einfu
at und formale Sprachen
¨ hrung in Berechenbarkeit, Komplexit¨
WS 2014/2015
Blatt 4
Aufgabe 1: Zeigen Sie mittels Reduktion, dass die folgende Sprache nicht entscheidbar ist.
L1 := { M |F¨
ur alle w ∈ {0, 1}∗ akzeptiert M Eingabe w genau dann,
wenn M Eingabe wR akzeptiert}.
Benutzen Sie bei Ihrer Reduktion das Halteproblem.
¯ die entsprechenden
Aufgabe 2: Seien A und B zwei beliebige Sprachen und seien A¯ und B
¨
Komplemente von A und B. Zeigen sie, dass folgende Aquivalenz gilt:
¯ reduzierbar.
A ist auf B reduzierbar ⇐⇒ A¯ ist auf B
Aufgabe 3: Zeigen Sie, dass das Akzeptanzproblem auf die folgende Sprache reduziert
werden kann.
ReachableState :=
( M , q, x)
bei Eingabe x gelangt die DTM M
mindestens einmal in den Zustand q.
Aufgabe 4: Sind die folgenden Sprachen rekursiv aufz¨ahlbar?
a) L2 := { M |M h¨alt bei h¨ochstens 42 Eingaben.}
b) L3 := { M |M h¨alt bei mehr als 42 Eingaben.}
Begr¨
unden Sie Ihre Antwort. Falls eine Sprache rekursiv aufz¨ahlbar ist, beschreiben Sie informal die Arbeitsweise einer DTM, die die Sprache akzeptiert. Andernfalls f¨
uhren Sie eine
Reduktion durch.

Download Report