Wann erkennt Turingmaschine ein Wort ?

Question

Hallo,

ich habe in der Vorlesung leider nicht ganz verstanden, wann eine Turing-Maschine ein Wort akzeptiert. Könnte das bitte jemand nochmal erklären?

Vielen Dank!

Answer 1

Hallo, 

(v1, s, v2) ist eine (akzeptierende) Endkonfiguration falls der Zustand s ein Endzustand ist und keine weitere Folgekonfiguration für (v1, s, v2) existiert.

Das heisst, wenn du einen Übergang mit einem Endzustand hast und du keinen weiteren Übergang findest, mit dem du weitermachen kannst, dann hat die Turingmaschine das Wort akzeptiert.

Noch henauer gesagt. Die Turingmaschine akzeptiert das Wort, wenn du ausgehen von deiner Anfangskonfiguration in (v1, s, v2 ) gelangst.

Ich hoffe das ich dir damit weiterhelfen konnte.

Grüße,

Jördis (Tutorin )

 

Answer 2

Hallo,

Eine Turingmaschine hält akzeptierend, falls sie in einem Endzustand ist und kein weiterer Übergang möglich ist. Sie ist also in einer akzeptierenden Endkonfiguration (v, s, w) mit v ist Bandinschrift links und w ist Bandinschrift rechts vom Schreib-Lese-Kopf und "s ist Element der Menge der Endzustände" und für (v, s, w) existiert keine Folgekonfiguration.

Viele Grüße

Christiane (Tutorin)