Printable View
I thought that I would go until the end of the input and then go back in the middle and insert a '#'. Then I know how to solve this problem. The input will have as first char a special symbol |_| and will end with this symbol too. So an example of accepted input would be this one:Code:w is in {a, b}^*
I do not know how to go back in the middle or how to measure the length of the input. I do not know however the tools to do that! Any idea?Code:|_|abaaba|_|
The algorithm will go like this:
Make the first char an upper one. Go to the last char and convert it to an upper one. Do this until no lower chars exist.
Now the "pointer" is set on the first letter of the 2nd string of the middle.
Make all the chars of the 2nd string (i.e. after the middle of the input, which we found as described above).
Then parse the input and when you have a match, place a blank. You are done when tape has only blanks.
Now, I do not know how to express this in Turing machine language, with δ() and all this, but I will have to search..
Yep, it worked. I did some modifications to my approach, but this should be enough for someone to get started. If someone wants more info, let me know. :)
I think you are making this needlessly complicated.
Replace 1st symbol with _
Traverse to the end of the input with a state that remembers what the 1st symbol was.
If matches, replace with _, go back and continue doeing the same for the smaller string.
Otherwise go to an invalid state and end.
Stop when all input is consumed.
This would work too! ;) Thnx!