Übung 10

Aufgabe 10.1:
(3+4 Punkte)
(a) L1 werde durch eine deterministische Turingmaschine T1 entschieden, L2 werde durch eine deterministische Turingmaschine T2 entschieden.
L3 werde durch eine deterministische Turingmaschine T3 entschieden.
Wir geben jetzt die Arbeitsweise einer deterministischen Turingmaschine T an, die L := L1 ∩ (L2 ∪
L3 ) entscheidet. w ∈ X ∗ sei die Eingabe in T .
1. arbeite auf T2 mit Kopie von w (erstellen aus w) als Eingabe
erreicht T2 Nichtfinalzustand, so zu [2.]
erreicht T2 Finalzustand, so zu [3.]
2. arbeite auf T3 mit Kopie von w (erstellen aus w) als Eingabe
erreicht T3 Nichtfinalzustand, so zu [4.]
erreicht T3 Finalzustand, so zu [3.]
3. arbeite auf T1 mit Kopie von w (erstellen aus w) als Eingabe
erreicht T1 Nichtfinalzustand, so zu [4.]
erreicht T1 Finalzustand, so zu [5.]
4. gehe in Nichtfinalzustand von T , d.h. lehne w ab. STOPP
5. gehe in Finalzustand von T , d.h. akzeptiere w ab. STOPP
(b) L1 werde durch eine deterministische Turingmaschine T1 akzeptiert, und L2 werde durch eine
deterministische Turingmaschine T2 akzeptiert.
Wir geben die Arbeitsweise einer deterministischen Turingmaschine T an, die L := L1 ∪ L2 akzeptiert. w ∈ X ∗ sei die Eingabe in T .
0. t := 0
1. t := t + 1, T erstellt eine Kopie von w (evtl. ausführlich erklären)
2. T wendet auf Kopie w das Programm von T1 t Takte an. Wird w dabei von T1 akzeptiert, so
akzeptiere T das Wort w. STOP. Sonst lösche alles außer w und t. Gehe zu 3.
3. T erstellt Kopie von w und wendet darauf das Programm von T2 t Takte an. Wird w dabei
von T2 akzeptiert, so akzeptiere T das Wort w. STOP. Sonst lösche alles außer w und t. Gehe
zu 1.
Aufgabe 10.2:
M ist entscheidbar.
Beweis:
Eingabe n
berechne 2n
for p = 3 to 2n − 1 step 2
for q = 3 to 2n − 1 step 2 do
teste, ob p und q Primzahlen sind (z.B. mit Sieb des Eratosthenes) und p + q = 2n
wenn ja, so akzeptiere n. STOPP
wenn nein, so lehne n ab. STOPP
(4 Punkte)
Aufgabe 10.3:
(4 Punkte)
⇒:
A sei semi-entscheidbar, d.h. es existiert eine DTM M , die A akzeptiert.
w ∈ L ⇔ M hält nach endlich vielen Schritten in einem Finalzustand zf .
DTM M ′ zur Berechnung von χ̂ arbeitet auf Eingabe w wie folgt:
• arbeite wie M auf Eingabe w
• wenn Halt in Finalzustand, so lösche Bandinschrift und schreibe 1 auf. STOPP
• wenn Halt in Nichtfinalzustand, so laufe unendlich lange weiter
• sonst wie M (unendlich lange weiter laufen)
⇐:
DTM M ′ berechne χ̂.
geben DTM M zur Akzeptierung von A an:
Eingabe: w
• arbeite wie M ′
• hält M ′ mit Bandinhalt 1, so gehe in Finalzustand (w akzeptiert)
• sonst laufe einfach unendlich lange weiter (wie M ′ )
Aufgabe 10.4:
(6 Punkte)
←:
L sei eine unendliche Sprache. Eine Turingmaschine Ta zähle die Elemente von L in quasilexikografischer Reihenfolge ohne Wiederholung auf.
Wir konstruieren eine Turingmaschine Te zur Entscheidung von L:
Eingabe sei x
1. Te berechnet l := |x|.
2. Te zählt (mithilfe von Ta ) die Elemente von L bis zur Länge l auf.
3. Te prüft, ob unter den aufgezählten Elementen das x ist.
Falls ja, so wird x akzeptiert. Falls nein, so wird x abgelehnt.
→:
Die Turingmaschine Te entscheide die Sprache L ⊆ Σ∗ . Eine Turingmaschine T ′ zähle alle Elemente
x0 , x1 , x2 , ... ∈ Σ∗ in quasilexikografischer Ordnung ohne Wiederholung auf.
Die L aufzählende Turingmaschine Ta arbeitet mithilfe von Te und T ′ wie folgt:
1. T ′ berechnet x = x0 .
2. Te wird auf der Eingabe x ausgeführt.
3. Wenn Te die Eingabe x akzeptiert, so gibt Ta das Wort x aus.
4. T ′ berechnet das quasilexikografisch nächste x.
5. Ta arbeitet bei 2. weiter.
Ta zählt offenbar die Elemente von L in quasilexikografischer Reihenfolge ohne Wiederholung auf.

Download Report