0
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Apr 19, 2014 at 6:59

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • $\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$ Commented Apr 19, 2014 at 9:54
  • $\begingroup$ @HendrikJan, you do string comparisons as you go. It's not that hard. $\endgroup$ Commented Apr 19, 2014 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$ Commented Apr 20, 2014 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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