a): Warum wird das weitere Sonderzeichen '#' benötigt ?

Question

da ich nicht verstehe, weshalb das # benötigt wird, habe ich wohl nicht verstanden, was die Sprache eigentlich vorschreibt und weshalb das  nötig ist. Könnte mir bitte jemand auf die Sprünge helfen? Vielen Dank.

Answer 1

Die Wörter der Sprache haben die Form x$x, d.h. es kommt zweimal hintereinander die selbe Folge von 0 und 1. Diese beiden Teile sind durch ein $ getrennt, also z. B. 01101$01101

Die Idee der TM in der Lösung ist, das erste Zeichen des linken Teils zu lesen, im Zustand zu speichern und dann nach rechts bis hinter das $ zu spulen. Dann wird das Zeichen rechts neben dem $ mit dem im Zustand gespeicherten verglichen. Unterschiedliches Zeichen -> TM bricht ab, Wort nicht akzeptieren. Wenn das Zeichen gleich ist, dann nach links spulen auf das zweite Zeichen der Eingabe und dieses mit dem zweiten Zeichen des rechten Teils vergleichen (auf die gleiche Weise) usw. Das Problem ist nun, dass x beliebig lang sein kann, man muss daher markieren, welche Zeichen man bereits verglichen hat, um das nächste unverglichene Zeichen bzw. die passende Stelle im rechten Teil  zu finden. Eine einfache Möglichkeit ist, alle Zeichen, die man bereits verarbeitet hat, mit # zu überschreiben. Dann kann man das nächste zu verarbeitende Zeichen leicht finden (das Zeichen rechts von #)

Gruß,

Tobias (Tutor)