Turingmaschine Endzustand |
| 18.03.2015, 11:31 | Auf diesen Beitrag antworten » | ||||||
| Svenz | Turingmaschine Endzustand Bitte gib hier Deine Frage ein. Welche Lösungsansätze sind Dir selbst dazu eingefallen? Was hast Du schon probiert? Bedenke, dass wir hier Hilfe zur Selbsthilfe leisten und keine Komplettlösungen liefern werden. Viel Erfolg! |
||||||
|
|
|||||||
| 18.03.2015, 11:32 | Auf diesen Beitrag antworten » | ||||||
| Svenz | 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, 15:11 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hallo Svenz, die TM hält nicht an wenn sie den Zustand Jetzt die Frage an dich: welche Konsequenz ergibt sich daraus? Gruß, Karlito |
||||||
| 18.03.2015, 16:39 | Auf diesen Beitrag antworten » | ||||||
| Svenz | 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? |
||||||
| Anzeige | |||||||
|
|
|||||||
| 18.03.2015, 18:08 | Auf diesen Beitrag antworten » | ||||||
| Karlito |
So sehe ich das auch.
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.
Das bedarf der Klärung des vorherigen Sachverhaltes. Gruß, Karlito |
||||||
| 18.03.2015, 19:04 | Auf diesen Beitrag antworten » | ||||||
| Svenz | Vielen Dank schonmal für deine Hilfe 
Gibt es vielleicht einen Unterschied zwischen Erkennen und Akzeptieren? |
||||||
| 18.03.2015, 19:29 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Ich glaube nicht. |
||||||
|
|
