Skip to main content
added 4 characters in body
Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

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 ...).

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).

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 ...).

Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

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).