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?
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?