Alternative Lösung Turingmaschine a^n b^n c^n (Vorlesung Bsp.)

Question

Hallo,

ich wäre Ihnen sehr dankbar wenn Sie einmal meine Lösung überprüfen könnten. Im Unterschied zur Vorlesung habe ich zwei Zustände weniger. Zustand s1 aus der Vorlesung erschien mir unnötig. Den andere spare ich mir in dem ich die beiden Zustände die an den Anfang des Wortes gehen, bündele. Am Ende gehe ich auch nicht mehr so durch das Wort wie in der Vorlesung.

Hier ein One Drive Link, da mich die Website leider keine Bilder hochladen lässt und es sonst ziemlich chaotisch wird.

https://1drv.ms/f/s!AgqZl5BdXNkv83zKgK1FnRTpIh7A   

 

Vielen Dank im Voraus!

 

R.O.

Answer 1

Hallo uqysn,

leider liegt mir das Beispiel aus der Vorlesung aktuell nicht vor. Könntest du bitte zusätzlich noch die Aufgabenstellung und die Musterlösung schreiben? Dann schaue ich mir beide Lösungen gerne an.

Viele Grüße
Hannah (Tutorin)

Comments

Hallo Hannah,

hier:

https://1drv.ms/f/s!AgqZl5BdXNkv9AJiN-sHdAg_coet

Vielen Dank!

Roman

---

Hallo Roman,

ich habe mir die Aufgabe einmal angeschaut und fasse kurz zusammen, was hier passiert: Zuerst läuft die Turingmaschine einmal durch das gesamte Wort, um zu checken, ob sich nur a, b und c in der richtigen Reihenfolge darin befinden, allerdings ohne zu zählen (Buchstabenreihenfolgenchecker). Danach läuft die TM vom Anfang des Worten bis zum Ende und markiert von jedem Buchstaben den jeweils ersten, indem sie ihn durch 1, 2 oder 3 ersetzt. Am Ende angekommen, läuft die TM rückwärts, allerdings nicht mehr bis ganz zum Anfang des Wortes, sondern nur bis zum ersten a nach der 1. Dann markiert sie wieder die jeweils nächsten a, b und c (Buchstabenmarkierer). Am Ende des Markierers steht die Maschine auf der ersten 2, weil es kein a mehr gibt. Jetzt ist allerdings nicht klar, ob es noch ein oder mehrere bs oder cs gibt. Daher wird das Wort noch einmal nach rechts durchlaufen. Falls das Teilwort nur noch aus 2 und 3 besteht, erreicht man den Endzustand S12, sonst bleibt man in S11 und das Wort wird nicht akzeptiert.
Jetzt zu deiner Lösung:
- Für meine Begriffe kannst du den Zustand S1 und den Pfeil zwischen den beiden S4 weglassen. Das passt. Was ich allerdings nicht als richtig erachte, ist bei deinem Zustand S4 das in rot geschriebene 3,3,L etc. Zu diesem Zeitpunkt wurde noch nichts ersetzt, also brauchst du das hier noch nicht.
- Dein roter Pfeil von S9 zu S4 ist auch nicht richtig, er sollte mit der Beschriftung auf S9 zeigen, also wie in der Vorlesung eine Schleife bilden. Erst wenn eine 1 eingelesen wird, gehst du zu deinem Zustand S5 zurück. Dann kannst du dir auch den Pfeil 1,1,R sparen, weil du nicht bis zum Anfang des Wortes gehst, sondern beim Pfeil zurück bereits wieder nach rechts gehst und dort nur noch as stehen.
- Die Idee, dass du das Wort am Ende von rechts nach links durchgehst, ist verständlich. Du musst allerdings darauf achten, dass du auch eine 3,3 auf der Schleife hat, mit der du das Wort wieder nach links durchgehst, um dann weiter zu markieren. Bei der deterministischen Turingmaschine muss allerdings deutlich gemacht werden, wohin die Maschine laufen soll.

Ich hoffe, die Antwort hat dir geholfen, sonst frag noch einmal nach.
Viele Grüße,
Hannah (Tutorin)

---

Hey Hannah,

schon mal vielen Dank!
Ein paar Fragen hätte ich noch.

"Zu diesem Zeitpunkt wurde noch nichts ersetzt, also brauchst du das hier noch nicht." Stimmt aber ich wollte mir einen Zustand sparen und habe deswegen nicht wie in der Vorlesung nochmal einen Zustand s10 definiert. Wenn ich also nach dem erstmaligen markieren wieder zu s4 gelange, weil das letzte Zeichen eingelesen wurde (sprich *) brauch ich die roten Zustände ja um wieder komplett an den Anfang des Wortes zu gelangen (Deswegen brauche ich aber auch bei s5 den Übergang 1, 1, R). Ob ich jetzt bis an den Anfang des Wortes gehe oder nur bis zum ersten nicht markierten 'a' sollte ja keine Rolle spielen (klar meine TM wäre etwas langsamer).
Durch den Pfeil von s9 zu s4 erzeuge ich ja prinzipiell eine ähnliche Schleife wie in der Vorlesung nur das bei mir am Anfang des Schleifendurchlaufs an den Anfang des Wortes gegangen wird, und nicht wie in der VL am Ende an den Anfang gegangen wird.
Dies kompensiere ich ja wieder damit, dass ich am Ende von links nach rechts überprüfe und nicht wie in VL von links nach rechts.

Weist du was ich meine oder habe ich noch einen Denkfehler?

Vielen Dank

Roman

---

Hallo Roman,
ich hatte vorhin übersehen, dass der Zustand 4 ja zwei Mal auf dem Papier ist und konnte daher die roten Zustandsübergänge nicht richtig zuordnen. So wie du es erklärst sollte es aber richtig sein.
Wie du schon richtig gesehen hast, ist deine TM etwas langsamer, weil du immer zum gesamten Anfang des Wortes zurückgehst, aber das sollte kein Problem darstellen.
Viele Grüße
Hannah (Tutorin)

---

Super, ja es ist leider etwas unübersichtlich.

Vielen Dank schönen Feiertag (;

Roman