Alternativlösung

Question

Ist folgende Überführungstabelle auch richtig?

Die TM überprüft also mit Sog und Sou, ob das Wort eine gerade Anzahl an Zeichen enthält.

Ist das nicht der Fall, geht die TM über in Sx, eine Senke, welche kein Endzustand ist.

Andernfalls geht die TM über Sz zurück zum ersten Zeichen, ersetzt dieses durch ein N oder ein E  und hängt hinten dementsprechend auch ein N oder E an das Wort an. Auf dem Rückweg in Szo wird die erste 0 oder 1 auch in ein N oder ein E umgewandelt, damit schließlich maximal das halbe Wort hinten angehängt wird. Danach wechselt die TM in Sz1, bis Sie wieder auf ein N oder E trifft, woraufhin die TM die Lese-/Schreibeinheit nach rechts bewegt und in Ss wechselt und wieder den selben Prozess durchläuft wie zuvor beschrieben.

Enthält das Wort nur noch Ns und Es wechselt die TM in SF und überschreibt alle Ns und Es mit einer 0 oder 1.

Über ein Feedback wäre ich sehr dankbar.

Viele Grüße

Answer 1

Hallo.

Ich weiß nicht ob du die Aufgabe ganz verstanden hast. Ich erkläre nochmal ganz kurz, was die Turingmaschine A können soll.
Das Wort 11001101010101 ist w 1100110 ist u, 1010101 ist v. |u| ist 7 und |v| ist auch 7. w hat also eine gerade Anzahl an Zeichen. Nun soll das Wort u nochmal hinten an uv geschrieben werden. Das Wort was rauskommen soll ist also 110011010101011100110. Das ist eine sehr komplexe Turingmaschine, wie du in der Lösung auch siehst. Deine Turingmaschine hat deutlich zu wenig Zustände um eine richtige Alternativlösung zu sein.

Außerdem ist deine Turingmaschine sehr schwer zu lesen.

Grüße, Felix(Tutor)

Comments

"Deine Turingmaschine hat deutlich zu wenig Zustände um eine richtige Alternativlösung zu sein. "
Was für eine Schande von einem Info-Tutoren so eine Aussage zu hören. In der Informatik werden gerade kurze und elegante Ansätze gesucht. Die angegebene Turingmaschine akzeptiert meiner Meinung nach genau die in der Aufgabenstellung angegebenen Wörter und ist außerdem um einiges kompakter als die der Musterlösung.  Ich denke Felix, du solltest dir die Überführungstabelle noch einmal genauer anschauen und ein fundiertes Argument dafür liefern, dass sie nicht korrekt ist!
salam alaikum

---

Hallo usdqz.
Du hast Recht, ich war wohl etwas zu sehr geprägt von der Lösung, dass ich mir nicht vorstellen konnte, dass diese Lösung richtig sei.
Bei der Erklärung hat mich das maximal so verwirrt, dass ich mir sicher war, der Student (hast du sie geschrieben usdqz?) hätte die Aufgabe nicht richtig verstanden.

Mit modernster Kamera und Entschlüsselungstechniken ist es mir mittlerweile gelungen alles auf dem Foto zu erkennen und ich muss zugeben:
Ich bin begeistert! Die Lösung funktioniert (Ich bin mir nicht ganz sicher, weil ich manche Zeichen wirklich nicht erkennen kann, aber der Ansatz ist klug und richtig!) und gibt genau die richtige Lösung. Die Übungsleiter werden begeistert sein von dieser schönen, eleganten und kurzen Lösung.  

Ich lasse meine erste Antwort nochmal stehen um an diese Schande zu erinnern!

Grüße, Felix(wahrscheinlich bald kein Tutor mehr, weil gefeuert)