Hauptklausur 2018 Aufgabe 4 Turingmaschine

Question

Hallo Hannah, 

das ist mir soweit klar. Danke!

Aber für den Zustand s3 und die Eingabe a ist ein Übergang definiert als (s3,a,R).

Woher weiß ich, dass ich aber schon bei (lambda, s3, acd) aufhören muss in meiner Konfigurationsfolge. Der nächste Übergang ist ja definiert, also dürfte die Turingmaschine doch noch nicht anhalten. Deswegen dachte ich, dass eben noch dieser eine Schritt hinzugefügt werden muss ...) |--- (lambda, s3,acd) |--- (a, s3,cd).

Erst dann gibt es für Zustand s3 und gelesenes Zeichen c keinen neuen Übergang mehr.

LG 

Answer 1

Hallo uvfaj,

die Konfiguration ist kommt nicht erst nach der Transition, sonst ist ein ergänzendes Element, das zu dieser Zeile gehört. Z.B. stehen wir in Zeile 1 auf dem a. Unser Zustand ist s0 und das aktuell eingelesene Zeichen a. Die aktuelle Konfiguration dazu ist (lambda, s0, a). Danach gehen wir über in den Zustand sx. In der zweiten Zeile stehen wir dann immer noch über dem a, unsere Konfiguration sieht ähnlich aus, nur dass wir uns in einem anderen Zustand befinden. Sie bezieht sich quasi immer auf die linke Seite der Transition.

Wenn wir uns jetzt noch einmal die vorletzte Zeile anschauen, sehen wir, dass wir in s3 sind und ein a einlesen. Unsere aktuelle Konfiguration ist eben jene, die rechts steht, wie du richtig gesehen hast. Danach gehen wir zwar einen Schritt nach rechts und schreiben die aktuelle Bandinschrift auch in die ganz letzte Zeile Allerdings existiert hier keine Transition mehr, weil der aktuelle Zustand nicht definiert ist und daher existiert auch keine Konfiguration. Wie oben gesagt, bezieht sich die Konfiguration auf deinen Zustand & das aktuelle Zeichen, wenn dies nicht definiert ist gibt es auch keine Konfiguration mehr.

Ich hoffe, jetzt ist es ein bisschen klarer geworden.

Viele Grüße

Hannah (Tutorin)