--- title: "TM accepting wwᴿ; process 101101" subject: "Theory of Computation" chapter: 4 key: "semester_3/theory_of_computation:tm-accept-wwr-101101" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-accept-wwr-101101 site: BCT Engineering --- # TM accepting wwᴿ; process 101101 Theory of Computation · Chapter 4: Turing Machine - Asked in: 2073 Chaitra - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-accept-wwr-101101 - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4 ## Question Design a Turing machine to accept the language L = {wwᴿ | w ∈ {0,1}*}. Show the processing for the string 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. ## Answer 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 | ```text 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) ```text [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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does each round of the TM do? A. Erases the first symbol, remembers it, goes to the last symbol and checks it matches, erases it, returns B. Marks the middle C. Counts the zeros D. Reverses the string Answer: A. Matching first and last symbols repeatedly checks the string is a palindrome. (Key point: Strategy) 2. Why does this machine reject odd-length strings such as 0? A. q0 never reads blanks B. After erasing the first symbol q2 or q4 finds a blank and has no move C. It accepts all strings starting with 0 D. It loops forever Answer: B. With a single symbol left, the check state meets a blank with no defined move, so it halts without accepting; wwR is always even. (Key point: Even length only) 3. When does the machine accept? A. When q0 reads a blank after all symbols are erased B. When q5 reads 0 C. When it reaches the right end D. When the first symbol is 1 Answer: A. An empty tape means every pair matched, so q0 sees a blank and goes to qa. (Key point: Accept condition) 4. What does q5 do? A. Moves left over 0, 1 until a blank, then right to q0 B. Checks the last symbol C. Accepts D. Moves right Answer: A. q5 returns the head to the left end so the next round starts at the first remaining symbol. (Key point: Return state) ## Related in Theory of Computation - [PDA for wwᴿ; accept abbbba](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-wwr-abbbba) — Theory of Computation, chapter 3 - [TM transforming ⊔w⊔ to ⊔ww⊔](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-copy-w-to-ww) — Theory of Computation, chapter 4 - [TM for f(w) = wwᴿ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-f-w-wwr) — Theory of Computation, chapter 4 - [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4 - [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4 - [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4 ## Related in other subjects - [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2 - [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4× - [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4× - [Steps in the design and synthesis process](https://www.bctengineer.com/question.md?key=semester_6%2Fmachine_design_i%3Adesign-process-steps) — Machine Design I, chapter 1