I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$:

$$L = \{ www \mid w \in \{a,b\}^+ \}$$

I'm not sure how to get started. Any hints would be appreciated.

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Apr 19 '14 at 6:59

You could copy the input to 3 tapes, then move the heads on tapes 2 and 3 until they point to the same substring and on tape 3, the end of substring matches the end of string.

The exact steps could be..

1. copy input
2. erase first symbol on tape two and first two symbols on tape three
3. go forward on all tapes until...
4. if one of the symbols is different than on other tapes, go back to the start of each tape and return to step 2
5. if tape three reaches end of input, you are done

  • $\begingroup$ "move the heads on tapes 2 and 3 until they point ..." That is hard given the fact these positions are not marked in the input. $\endgroup$ Apr 19 '14 at 9:54
  • $\begingroup$ @HendrikJan, you do string comparisons as you go. It's not that hard. $\endgroup$ Apr 19 '14 at 11:40
  • $\begingroup$ But string comparisons is much harder than the copying part in your hint, in my view. I would compute the position by dividing into 3, which is a nice trick when having two tapes. $\endgroup$ Apr 20 '14 at 0:50

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.