Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in TUR-AE

Beantwortet: S2 überflüssig

Fri, 27 Jan 2017 20:48:53 +0000

Ja, da in der Aufgabenstellung nicht gefordert ist, dass der Lesekopf beim Akzeptieren wieder auf dem linkesten Bandzeichen stehen muss, ist deine Lösung auch korrekt.

Viele Grüße

Philipp (Tutor)

Beantwortet: Übergangszustand

Tue, 14 Jul 2015 06:34:34 +0000

Hallo,

hier ist es schon wichtig den Zustand zu wechseln. Wir wollen bei dieser Turingmaschine, die Anzahl der Einsen zählen. Wenn du den Zustand nicht ändern würdest sondern bei der Eingabe einer 1 im Zustand s_{0} in s_{0} verbleibst, kannst du nicht mehr sehen ob es eine gerade oder ungerade Anzahl von Einsen war die auf dem bisher gelesenen Band stand.

Es gibt hier ja nur 2 Möglichkeiten (nur bezogen auf die 1, da uns die 0 in diesem Fall nicht interessiert):

Gerade Anzahl von Einsen (0x1 zählt auch dazu) → du bist in s_{0}, da die Maschine bei der 2. eingegebenen 1 (zu diesem Zeitpunkt ist sie in s_{1} wieder in s_{0} springt. Kommst an einen "*", schreibst nichts, und springst in s_{2} der bis zum Anfang färhrt um anschließend in s_{e} zu wechseln und den Vorgang zu beenden.
Ungerade Anzahl von Einsen → du bist in s_{1}, kommst zu einem "*", schreibst eine 1 hinzu und wechselst zu s_{2} in dem wieder bis zum Anfang gefahren wird und in den Endzustand s_{e} gewechselt wird.

In beiden Fällen wird der Zustand nicht geändert wenn eine 0 kommt, da uns diese nicht interessiert.

Ich hoffe so wurde das ganze verständlicher ;)

Noch viel Erfolg beim Lernen!

Viele Grüße,

Marc (Tutor)

Beantwortet: Endzustand

Mon, 02 Feb 2015 22:52:38 +0000

Hallo,

ein Übergang der Form (s0,*) -> (se,0,N) ist zulässig, ebenso (s1,*) -> (se,1,N). s2 wird hier genutzt, um den Lesekopf wieder ganz nach Links zu bewegen. Da dies von der Aufgabenstellung nicht verlangt wird, ist es an sich auch nicht nötig.

Ob eine Lösung mit mehr Zuständen richtig ist, kann ich ohne selbige zu sehen schwer sagen. Prinzipiell muss eine Lösung aber nicht minimal sein.

Viele Grüße,

Julian (Tutor)

Beantwortet: S/L Kopf

Wed, 22 Oct 2014 11:24:25 +0000

Ist in der Aufgabe nichts anderes angegeben, kann immer davon ausgegangen werden, das der S/L Kopf sich zu Beginn über dem linkesten Zeichen des Wortes befindet. Das gilt auch für Klausuren.

Sofern es nicht explizit angegeben ist, ist es egal wo der SLK hält, man muss ihn also auch nicht wieder in die Startposition bringen und es kann mehrere richtige Lösungen geben.