As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one.
Use a Turing machine of one tape and "pointer".
An idea:
I thought that I would do something like R_until_end, then go back in the middle, add a special symbol like '#' and then I know how to tackle the problem. However, how would I fint the middle of it?
UPDATE:
- 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..
DONE:
- 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. 🙂
SOLUTION-2nd:
- 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.
source
Best Answer
Edited to redact palindromic assumption. Sorry for the confusion!
After thinking about it more, I would approach it first by counting the length of the string. If it is odd, reject. Otherwise, partition the string in half. So you want to test if i and (n/2 + i) are the same, where $n$ is the length of the string. The state transitions would be similar as if you were dealing with a palindrome. So that's a good place to start.