Ich habe den ganzen Monat gebraucht, um dieses Problem zu lösen, da ich es aus dem Buch einer Übung habe, und ich würde gerne wissen, wie man das in eine Turingmaschine schreibt; ich würde das wirklich gerne lernen. Könnte mir bitte jemand helfen?
Denken Sie an die letzten beiden Buchstaben Ihres Logins (wenn beide Buchstaben gleich sind, wählen Sie bitte den nächsten Buchstaben im lateinischen Alphabet als zweites Symbol). Schreiben Sie eine Turing-Maschine die die Sprache Stretch(x+1) erkennen kann. Dies ist die Sprache aller Zeichenketten, die eine fortlaufende Folge von Vorkommen der beiden Buchstaben enthalten, gefolgt von '*', gefolgt von einer weiteren Buchstabenkette mit x+1 Vorkommen des jeweiligen Buchstabens, wobei in der ersten Buchstabenkette ein einziges Mal vorkam. Hier ist x = 1. Die Eingabe für die Maschine sind nicht-null Zeichenfolgen von a, b, *. Zum Beispiel Beispiel: Wenn die Buchstaben "a" und "b" sind (und x=1), dann sind aba*aabbaa, bb*bbbb und baab*bbaaaabb sind in der Sprache enthalten, aber abb*abbb nicht. Sie können davon ausgehen, dass Sie Unterprogramme haben, um 0 in die erste Zelle zu schreiben und den Rest des Bandes zu löschen und um 1 in die erste Zelle zu schreiben und den Rest des Bandes zu löschen.
Ich würde es sehr schätzen, wenn Sie mir helfen könnten.
