0
$\begingroup$

I know that for the language ww, the TM can zig zag across the tape and match symbols to see if the strings are equivalent by first finding the midpoint of the string. However I am lost on how the TM can find out where in www the repeated strings start and stop. I can find midpoint but how do I get one third or two thirds of the string. Any tips to get me started?

$\endgroup$
0
$\begingroup$

Let $\ell$ be the length of the input. You can assume w.l.o.g. that $\ell=3k$ for some integer $k$. If this is not the case (which can be easily checked by your TM), then the answer is trivial.

The problem boils down to finding $k$. In order to do so you can use the following strategy:

  1. "mark" the two rightmost unmarked tape cells;
  2. "mark" the leftmost unmarked cell;
  3. If the cell immediately to the right of the current head position is marked, then you are done since the head must be in position $k$. Otherwise, repeat from step 1.
$\endgroup$
0
$\begingroup$

Steven suggested one solution. I've already tried something similar, basically you need to find the word w at the beginning. Then you check the whole input.
You outlined a difficult problem. You may find out over time, but here is a link where it is written in abbreviated form and also with a graph.

https://www.geeksforgeeks.org/turing-machine-for-language-www-w-a-b/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.