- 2073 Chaitra
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.
| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | ⊔ | same | S | qa |
| q0 | 0 | ⊔ | R | q1 |
| q0 | 1 | ⊔ | R | q3 |
| q1 | 0 / 1 | same | R | q1 |
| q1 | ⊔ | same | L | q2 |
| q3 | 0 / 1 | same | R | q3 |
| q3 | ⊔ | same | L | q4 |
| q2 | 0 | ⊔ | L | q5 |
| q4 | 1 | ⊔ | L | q5 |
| q5 | 0 / 1 | same | L | q5 |
| q5 | ⊔ | same | R | q0 |
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)
Related questions
- PDA for wwᴿ; accept abbbba · Theory of Computation, chapter 3
- TM transforming ⊔w⊔ to ⊔ww⊔ · Theory of Computation, chapter 4
- TM for f(w) = wwᴿ · Theory of Computation, chapter 4
- Multitape TM as copying machine · Theory of Computation, chapter 4
- Define multitape Turing machine · Theory of Computation, chapter 4
- What is a Turing machine; its operation · Theory of Computation, chapter 4
- Construct FSA accepting reverse language · Discrete Structure, chapter 2
- Design FSA accepting even number of a's · Discrete Structure, chapter 2 · asked 4×
- Design FSA accepting odd number of b's · Discrete Structure, chapter 2 · asked 4×
- Steps in the design and synthesis process · Machine Design I, chapter 1