Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2016-B-02

Beantwortet: verstandnis

Tue, 04 Jan 2022 10:07:47 +0000

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.

Beantwortet: Wieso ist das leere Wort erlaubt?

Tue, 26 Jan 2016 11:12:13 +0000

Hallo uwdtl,

prinzipiell starten Turingmaschinen in der Anfangskonfiguration $( \lambda , s_0 , w )$ , also mit dem Lesekopf über dem linkesten Zeichen der Bandinschrift. Wäre das erste Zeichen bereits ein Leerzeichen (und damit die Bandinschrift das leere Wort) würde die Turingmaschine in der Tat stoppen und das Wort akzeptieren.

Viele Grüße

Jonas (Tutor)

Beantwortet: Lösung unverständlich-> Alternativlösung möglich?

Mon, 25 Jan 2016 13:45:31 +0000

Ihre Lösung ist leider nicht richtig. Wie kommen Sie darauf, dass 011111, oder 10000 akzeptiert werden? Sie können mit dem XWizard sehen, dass das nicht der Fall ist: http://www.xwizard.de:8080/Wizz?lang=ger&hide=.i2&template=ID-8657#Output

Die Turingmaschine akzeptiert nur Wörter, bei denen auf jede 0 oder auf jede 1 ein S folgt. Ihre Wörter müssten so aussehen:

0S11111 oder 01S1S1S1S1S oder 0S1S1S1S1S1S

(Und ebenso für das andere Wort.)

Viele Grüße

Lukas König