 Turingmaschine Endzustand |
Svenz
unregistriert
 |
|
|
18.03.2015 11:31 |
|
|
Svenz
unregistriert
|
|
Ups, da ist was schiefgelaufen. Mein Post:
Hallo,
ich habe eine Frage zur Turingmaschine und zwar wann genau diese stoppt, bzw. ein Wort erkennt.
Diese Aufgabe macht mich nachdenklich:
"Siehe Anhang vorheriger Post"
Stoppt die Maschine nun sofort wenn sie q1 erreicht?
Also würde sie die Sprache a*b erkennen? Oder würde sie q1 weiter durchlaufen und a*ba* erkennen?
Bin da etwas verwirrt und im Internet finden sich auch verschiedene Lösungen.
Bin für Hilfe dankbar.
|
|
|
18.03.2015 11:32 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
18.03.2015 15:11 |
|
|
Svenz
unregistriert
|
|
Das müsste ja eigentlich heißen, dass die TM kein Wort erkennt, da q2 kein Endzustand ist.
Nun hab ich in der Vorlesung aber auch folgendes gehört: Zum Erkennen eines Wortes muss die Turingmaschine das Wort nicht zwingend bis
zum Ende lesen, sie muss nicht einmal stoppen. Es genügt das Erreichen/Durchlaufen
eines Endzustands, um ein Wort zu akzeptieren.
Oder heißt das nun, wenn ich der TM z.b. nur ein b zum lesen gebe, dann steht am Ende bb auf dem Band und der Zustand ist q2. Das Wort b wurde jedoch trotzdem erkannt?
|
|
|
18.03.2015 16:39 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| Zitat: |
Original von Svenz
Das müsste ja eigentlich heißen, dass die TM kein Wort erkennt, da q2 kein Endzustand ist.
|
So sehe ich das auch.
| Zitat: |
Original von Svenz
Nun hab ich in der Vorlesung aber auch folgendes gehört: Zum Erkennen eines Wortes muss die Turingmaschine das Wort nicht zwingend bis
zum Ende lesen, sie muss nicht einmal stoppen. Es genügt das Erreichen/Durchlaufen
eines Endzustands, um ein Wort zu akzeptieren.
|
Allen (zwei) Definitionen, die ich kenne ist gemein, dass sie im akzeptierenden Zustand stoppen müssen. Ich könnte mir eine Variante vorstellen, bei der ein Finalzustand nur durchlaufen werden muss, möchte aber jetzt nicht Beweisen, dass das ausreicht und kann dadurch auch nicht sagen, ob diese Möglichkeit besteht. Eine nicht stoppende TM kann jedoch meiner Meinung nach nicht akzeptierend sein. Bitte kläre das noch eimal. Ich schätze Du verwechselst das mit der Nicht-Akzeptanz. Dabei spielt es keine Rolle ob ein Finalzustand durchlaufen wird oder die TM nicht anhält. Ein Wort gilt als nicht akzeptiert, wenn die TM in einem Nicht-Finalzustand anhält oder nie anhält. D.h. selbst wenn unendlich lange im Finalzustand verweilt wird, so wird das Wort nicht akzeptiert. Das ergibt sich auch aus der Definition von Wörtern, welche immer eine endliche Länge haben müssen.
Edit: Dass das Wort nicht bis zum Ende gelesen werden muss ist auch laut den mir bekannten Definitionen korrekt.
| Zitat: |
Original von Svenz
Oder heißt das nun, wenn ich der TM z.b. nur ein b zum lesen gebe, dann steht am Ende bb auf dem Band und der Zustand ist q2. Das Wort b wurde jedoch trotzdem erkannt? |
Das bedarf der Klärung des vorherigen Sachverhaltes.
Gruß,
Karlito
|
|
|
18.03.2015 18:08 |
|
|
Svenz
unregistriert
|
|
Vielen Dank schonmal für deine Hilfe 
Gibt es vielleicht einen Unterschied zwischen Erkennen und Akzeptieren?
|
|
|
18.03.2015 19:04 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
18.03.2015 19:29 |
|
|
|
