| Die letzten 7 Beiträge |
| Karlito |
Ich glaube nicht. |
| Svenz |
Vielen Dank schonmal für deine Hilfe 
Gibt es vielleicht einen Unterschied zwischen Erkennen und Akzeptieren? |
| Karlito |
| 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 |
| 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? |
| Karlito |
Hallo Svenz,
die TM hält nicht an wenn sie den Zustand ![[latex]q_1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_1) erreicht. Die TM hält an, wenn es keine folgenden Übergänge mehr gibt. Wenn wir uns die TM anschauen (s.Anhang), so gibt es eigentlich immer einen Folgeübergang außer wenn ein Blank gelesen wird. Dann geht die TM in den Zustand ![[latex]q_2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_2) und hält an.
Jetzt die Frage an dich: welche Konsequenz ergibt sich daraus?
Gruß,
Karlito
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| 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. |
| 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!
Svenz hat dieses Bild (verkleinerte Version) angehängt:
|
|
|
