How would I go about making a Turing machine to accept the following language L?

$$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$

I was thinking counting the number of symbols in the input string and then dividing by three to find the beginning of each instance of w and then testing if each instance is the same, but this seems a bit roundabout.

I feel like there is a way by marking the first three symbols and then moving the 2nd and 3rd markers until the strings in between them are the same but I'm having a hard time articulating this into an algorithm.

Can anyone point me in the right direction?


1 Answer 1


From the comment: a quick way is to think that you are working on a two-tapes TM (initially the second tape is empty). You start placing $abc$ on it; then continue scanning it expanding the $a$, $b$ and $c$ substrings ($aabbcc,aaabbbccc,aaaabbbbcccc,...$) until the length of the second string matches the length of the input (or reject if you "overflow" it). During a scan simply replace the first $b$ with 1 $a$, the first 2 $c$s with 2 $b$s and append 3 $c$s at the end.

   Input: 011010110101101
2nd tape: <empty>
  Scan 1: abc
  Scan 2: aabbcc 
  Scan 3: aaabbbccc
  Scan 4: aaaabbbbcccc
  Scan 5: aaaaabbbbbccccc

At this point it should be easy to check if the three subwords are equal ... finally think how to "merge" the second tape into a single one (just add extra symbols to the tape alphabet ...).


Your Answer

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

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