---
title: "TM for f(w) = wwᴿ"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-f-w-wwr"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-f-w-wwr
site: BCT Engineering
---

# TM for f(w) = wwᴿ

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2071 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-f-w-wwr
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Design a TM for f(w) = wwᴿ, w ∈ {0,1}*. If your input is #01#, the TM should give #0110#.

## Short answer

The TM marks the rightmost unmarked symbol of w (x for 0, y for 1), appends a copy (a for 0, b for 1) after the right #, adds a new #, and repeats leftwards. When the left # is reached, marks are converted back. For #01#, output is #0110#.

## Answer

**Idea.** The tape holds #w#. Process w from its **right end** towards the left: take the rightmost unmarked symbol of w, mark it, and append a copy at the end of the tape (just before a new right-end #). The appended symbols then appear in the order of wᴿ. Use marks x, y for processed 0, 1 and a, b for appended 0, 1. At the end, convert the marks back.

M has states q0 ... q2, qA, qB, qW, qC and halting state qa, tape alphabet {0, 1, #, x, y, a, b, ⊔}.

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | # | same | R | q1 |
| q1 | 0 / 1 | same | R | q1 |
| q1 | # | same | L | q2 |
| q2 | 0 | x | R | qA |
| q2 | 1 | y | R | qB |
| q2 | x / y / a / b | same | L | q2 |
| q2 | # | same | R | qC |
| qA | 0 / 1 / x / y / a / b | same | R | qA |
| qA | # | a | R | qW |
| qB | 0 / 1 / x / y / a / b | same | R | qB |
| qB | # | b | R | qW |
| qW | ⊔ | # | L | q2 |
| qC | x / a | 0 | R | qC |
| qC | y / b | 1 | R | qC |
| qC | # | same | S | qa |

- q0, q1: go to the right-hand #, then back one cell into w.
- q2: scan left for the rightmost unmarked 0/1 (skipping x, y, a, b).
- qA / qB: carry a 0 / 1 to the end of the tape; write a / b over the old # and a new # after it (qW).
- qC: reached the left #; sweep right and convert x, a to 0 and y, b to 1.

#### Processing #01# (expected #0110#)
```text
[q0]#01#
#[q1]01#
#0[q1]1#
#01[q1]#
#0[q2]1#
#0y[qB]#
#0yb[qW]
#0y[q2]b#
#0[q2]yb#
#[q2]0yb#
#x[qA]yb#
#xy[qA]b#
#xyb[qA]#
#xyba[qW]
#xyb[q2]a#
#xy[q2]ba#
#x[q2]yba#
#[q2]xyba#
[q2]#xyba#
#[qC]xyba#
#0[qC]yba#
#01[qC]ba#
#011[qC]a#
#0110[qC]#
#0110[qa]#
```

The result is **#0110#** = # w wᴿ # for w = 01.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the main idea of the TM that computes w w^R?
   A. Copy w left to right at the end
   B. Take the rightmost unmarked symbol of w, mark it and append a copy at the end
   C. Reverse w in place
   D. Delete w and write it twice
   Answer: B. Processing from the right and appending each symbol builds w^R after w. (Key point: Idea)

2. What is the purpose of the marks x, y and a, b?
   A. x, y mark processed 0, 1 and a, b are the appended 0, 1, converted back at the end
   B. They mark the ends of the tape
   C. They are accepting symbols
   D. They count the length of w
   Answer: A. Marks distinguish original processed symbols from appended copies so they are not processed again. (Key point: Marks)

3. What does state qC do?
   A. Copies symbols
   B. Sweeps right converting x, a to 0 and y, b to 1
   C. Rejects
   D. Moves to the end
   Answer: B. After the left # is reached, qC restores the marks to 0 and 1. (Key point: Final step)

4. For input #01#, what is on the tape at the end?
   A. #0101#
   B. #1001#
   C. #0110#
   D. #1010#
   Answer: C. The output is # w w^R # = #01 10# = #0110#. (Key point: Result)

## Related in Theory of Computation

- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4
- [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
- [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
- [DFA starts or ends with 01](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-starts-or-ends-01) — Theory of Computation, chapter 2
- [Configuration of DFA; DFA with 01 and 10](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-config-01-and-10) — Theory of Computation, chapter 2
- [TM computing f(n) = n + 1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-increment-binary) — Theory of Computation, chapter 4

## Related in other subjects

- [Random process; LTI output is WSS if input is WSS](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Arandom-process-lti-wssp) — Communication Systems, chapter 9
- [Data logger input scanner and conditioner design](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Adatalogger-three-transducers) — Instrumentation II, chapter 5
- [Sallen-Key LPF at 10 kHz, largest C 0.01 μF](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Asallen-key-10khz-largest-capacitance) — Filter Design, chapter 6
- [Should technicians also be good citizens](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Aeven-best-technicians-good-citizens) — Communication English, chapter 2, asked 2×