0 Daumen
302 Aufrufe

Aufgabe

Entwerfe für jeden Aufgabenteil eine Turingmaschine M, welche Folgendes leistet:

a) M akzeptiert die Sprache L={0,1}+. Am Ende der Berechnung steht nur noch das letzte Zeichen der Eingabe auf dem Band.

b)M akzeptiert die Sprache L={w∈{0,1}+ | w ist die Binärdarstellung einer ganzen Zahl n mit 1024 ≤ n <4096}.

c)M akzeptiert die Sprache L={w∈{0,1}+| w ist die Binärdarstellung einer ganzen Zahl n >0} und am Ende einer akzeptierenden Berechnung befindet sich die Zahl 2n−1(in Binärdarstellung) auf dem Band.

Hinweis:Beachten Die Binärdarstellung einer natürlichen Zahl kann beliebig viele führende Nullen enthalten kann.

-----

Ansatz: ich weiß, dass eine Turingmaschine zunächst das erste Zeichen liest und dann weitergeht bis ein neuer Buchstabe kommt Wenn ein neuer Buchstabe kommt geht, man weiter bis zum Blanksymbol. In der Vorlesung wurde das Beispiel gebracht: a^x * b^x = aaaabbbb. Man läuft von a bis zum ersten b. Dann vom b bis zum ersten Blanksymbol. Vom Blanksymbol wird wieder in A zurückgelaufen, u.s.w, so dass sich das von links und rechts aufbaut.

Zur Teilaufgabe a) sind zudem die Lösungen geleakt worden.

L = {0,1}+ = {0,1} \ {ε }
M = {Q, Σ, δ , Γ, q_0, F)

Q = {q_0, q_1, q_2}
Σ = {0,1}
T = Σ ∪ {B}

Startzustand q_0
Übergangsfunktion q_0
δ (q_0, 0) = (q1, 0, rechts)
δ (q_0, 1) = (q1, 1, rechts)
δ (q_1, 0) = (q1, 0, rechts)
δ (q_1, 1) = (q1, 1, rechts)
δ (q_1, B) = (q2, B, rechts)

Was ist damit gemeint? Vom Zustand q_0 kommt man mit dem Zeichen 0 in den Zustand q1 mit Zeichen und verschiebt den Lesekopf nach rechts. Eine Zeile später ist man jedoch wieder in Zustand q_0. Wie kamen die auf die Lösung?
Um Punkte auf die Aufgabe zu bekommen, muss zudem M = {Q, Σ, δ , Γ, q_0, F) für jede Teilaufgabe genau definiert sein

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community