verstandnis

Question

Wie lese ich ein?

Können Sie Schritt für Schritt erklaren?

                                 Danke

Answer 1

Hallo uqyxt,

ich bin mir nicht ganz sicher, ob ich deine Frage richtig verstanden habe, falls nicht, frag einfach noch einmal nach.

Wie ich es verstanden habe ist, wie man bei einem Wort vorgeht, um zu prüfen, ob das Wort akzeptiert wird oder nicht. Ich nehme mal das erste Beispielwort SS0S110S10S1.

Man beginnt immer mit dem linken Zeichen des Wortes, hier also S (links und rechts stehen noch unendlich viele * aber die sind zunächst nicht relevant).

Bei der Definition T=(...) steht, was der Anfangszustand ist, hier s0. Dann geht man in die Zeile mit dem aktuellen Zustand und nimmt das aktuelle Zeichen (S) für die Spalte. {(s0,S,R)} bedeutet, wir bleiben im Zustand s0, überschreiben das S mit S (ändern also nichts) und gehen ein Zeichen weiter nach rechts, im Beispiel das zweite S (das bedeutet das R. L würde bedeuten nach links zu gehen und bei N bleibt man auf dem aktuellen Zeichen stehen).
Wenn bei einem Zustand mehrere Tupel stehen (wie bei s0-0 zum Beispiel) muss man alle überprüfen bzw.  so lange, bis ein Weg funktioniert. Das Wort wird akzeptiert, wenn alle Zeichen abgearbeitet sind (bzw. genauer: nichts neues mehr kommt, wir also in eine leere Menge davor hatten) und die Turingmaschine in einem Endzustand ist, hier nur s0.

Noch einmal zurück zum Beispiel, beim dritten Zeichen, der 0 haben wir die Möglichkeit in den Zustand s10 oder s11 zu wechseln und wir bleiben auf dem Zeichen stehen und lassen auch die 0 stehen.
1. Fall wie gehen in s11 und fahren fort. Hier kommt es beim 5. Zeichen, der 1 aber zu einem Problem, wir landen in der leeren Menge, ohne in einem Endzustand zu sein, dass heißt, das Wort wird nicht akzeptiert.

2. Fall wenn wir in s10 gehen kommt es zu keinen Problemen und das Wort wird akzeptiert, da wir am Ende auf * stehen (das Zeichen neben der letzten 1) also alles abgearbeitet haben und im letzten Schritt in s0 gewechselt sind.