6 Tupel angeben bei Turingmaschine?

Ich hoffe dass diese Frage jetzt nicht den "Shitstorm of Doom" beschwört, da es allein auf dieser Seite gefühlt 713 Fragen zur Turingmaschine gibt, aber ich dromm' grad nicht kauf...äh...komm' grad nicht drauf..

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.

(und aus irgendwelchen Gründen bekomm' ich die Fettschrift an der Stelle hier nicht weg. Diesen Absatz bitte nicht mit aggressiven Schreien assozieren. Danke und LG

Computer, Schule, Mathematik, Mathe, rechnen, Automat, Informatik, Uni
3 Antworten

Meistgelesene Fragen zum Thema Automat