FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Theoretische Informatik (HS)

Turing-Maschine als Akzeptor von Sprachen

Turing-Maschine als Akzeptor von Sprachen 2007-09-23 23:55
Fred
Ich versuche mich gerade daran, eine Turing-Maschine zu finden, welche die Sprache {0^n 1^n 0^n | n >= 0} akzeptiert.

Als Eingabealphabet verwende ich {0, 1} und als Bandalphabet {0, 1, 2, #}. Die 2 soll für "markiert" stehen. Das Schweinegatter muss ich explizit angeben, oder?

Also meine Turing-Maschine sieht bisher so aus, sie ist aber definitiv noch falsch:

[img]http://img218.imageshack.us/img218/231/0n1n0nsm3.jpg[/img]

Zunächst schaue ich, ob das erste Zeichen das Schweinegatter ist. Dann ist nämlich n=0, und w = epsilon soll ja akzeptiert werden. Also zum Endzustand übergehen.

Ansonsten überspringe ich alle bereits markierten Ziffern (am Anfang sind noch keine markiert). Die erste gefundene 0 markiere ich. Dann werden alle weiteren Nullen und markierten Zahlen übersprungen, bis eine 1 gefunden wird, welche ebenfalls markiert wird. Dann werden analog alle weiteren Einsen und markierten Zahlen übersprungen, bis eine 0 gefunden wird, welche markiert wird.

Dann schauen wir, ob wir am Ende des Arbeitsbandes angekommen sind. Falls ja, sind alle Zahlen markiert, und wir gehen in den Endzustand über. Ansonsten spulen wir zurück und fangen wieder von vorne an.

Ich sehe gerade, dass die kursiv geschriebene Aussage nicht stimmt: es sind nur alle Nullen am Ende des Worts markiert. Also ist die akzeptierte Sprache wahrscheinlich {0^(n+a) 1^(n+a) 0^n | n,a>=0}. Richtig?

Wahrscheinlich muss ich nach der Markierung der letzten Null und Lesen des Schweinegatters das ganze Wort rückwärts durchlaufen, um zu überprüfen, ob auch wirklich alle Zahlen markiert sind. Sobald eine nicht markierte Zahl gefunden wird, muss ich einen Weg betreten, der zu einer neuen Iteration führt. Wird dieser Weg beim Zurückspulen nicht betreten, dann wird das Wort akzeptiert. Macht das Sinn? Oder sollte ich diese Unterscheidung schon beim "Vorspulen" treffen?

RE: Turing-Maschine als Akzeptor von Sprachen 2007-09-24 00:16
f0k
Wahrscheinlich muss ich nach der Markierung der letzten Null und Lesen des Schweinegatters das ganze Wort rückwärts durchlaufen, um zu überprüfen, ob auch wirklich alle Zahlen markiert sind. Sobald eine nicht markierte Zahl gefunden wird, muss ich einen Weg betreten, der zu einer neuen Iteration führt. Wird dieser Weg beim Zurückspulen nicht betreten, dann wird das Wort akzeptiert. Macht das Sinn? Oder sollte ich diese Unterscheidung schon beim "Vorspulen" treffen?
Klingt nach 'ner guten Idee. Bis auf den Teil mit der neuen Iteration, die brauchst Du nicht. Vom Zustand auf Deiner Zeichnung ganz rechts könntest Du mit ##L in einen neuen Zustand wechseln, der mit 22L zu sich selbst und mit ##R zum Endzustand führt. Wenn Du bei diesem "Zurückspulen" auf was anderes als eine 2 oder ein # triffst, kann das Wort nicht der Eingabesprache entsprechen, da musst Du also nichts vorsehen.

Kennst Du übrigens JFlap? Ganz gut, um Turing-Maschinen und Automaten zu basteln und zu testen.

RE: Turing-Maschine als Akzeptor von Sprachen 2007-09-24 00:29
Fred
Klingt nach 'ner guten Idee. Bis auf den Teil mit der neuen Iteration, die brauchst Du nicht.
Vielen Dank [23]