Skip to main content

TM accepting wwᴿ; process 101101

Short answer

The TM erases the first symbol, travels to the last symbol checking match, erases it, and returns left. Repeat; accept if tape blank. For 101101: matches 1-1, 0-0, 1-1, tape becomes blank, so accepted.

Design a Turing machine to accept the language L = {wwᴿ | w ∈ {0,1}*}. Show the processing for the string 101101.

L = { wwᴿ : w ∈ {0,1}* } is the set of even-length palindromes.

Idea. Repeat: erase the first symbol, remember it, travel to the last symbol and check that it is the same, erase it, return to the left. If the whole string is erased, accept. If the last symbol differs, or only one symbol was left (odd length), reject.

States: q0 start/look at the first symbol; q1 (first symbol was 0) and q3 (it was 1) travel right; q2 and q4 check that the last symbol is 0 or 1; q5 returns left. Accepting state qa.

StateReadWriteMoveNext
q0⊔sameSqa
q00⊔Rq1
q01⊔Rq3
q10 / 1sameRq1
q1⊔sameLq2
q30 / 1sameRq3
q3⊔sameLq4
q20⊔Lq5
q41⊔Lq5
q50 / 1sameLq5
q5⊔sameRq0
   q0 --0/⊔,R--> q1 (loop 0,1 R) --⊔/L--> q2 --0/⊔,L--> q5
   q0 --1/⊔,R--> q3 (loop 0,1 R) --⊔/L--> q4 --1/⊔,L--> q5
   q5 (loop 0,1 L) --⊔/R--> q0        q0 --⊔--> qa

Processing 101101 (w = 101)

[q0]101101
  erase first 1, travel right, last symbol is 1: erase it
⊔[q0]0110⊔        round 1 done, tape ⊔0110⊔
  erase 0, last symbol is 0: erase
⊔⊔[q0]11⊔⊔        round 2 done
  erase 1, last symbol 1: erase
⊔⊔⊔[q0]⊔⊔⊔        tape empty, q0 reads ⊔  -> qa (accept)

Each round matches the first and last remaining symbols (1-1, 0-0, 1-1), so 101101 is accepted. For 10, the first symbol 1 sends the machine to q3 and then q4, which reads 0 instead of 1 and has no move, so it halts without accepting (reject). For 0, the machine finds only a blank at q2 and also rejects.

✓ Answer checked by Claude Opus 5.5 (high effort)

All Theory of Computation chapter 4 questions →