- 2071 Chaitra
TM for f(w) = wwᴿ
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#.
Design a TM for f(w) = wwᴿ, w ∈ {0,1}*. If your input is #01#, the TM should give #0110#.
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#)
[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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- TM accepting wwᴿ; process 101101 · Theory of Computation, chapter 4
- TM transforming ⊔w⊔ to ⊔ww⊔ · Theory of Computation, chapter 4
- PDA for wwᴿ; accept abbbba · Theory of Computation, chapter 3
- DFA starts or ends with 01 · Theory of Computation, chapter 2
- Configuration of DFA; DFA with 01 and 10 · Theory of Computation, chapter 2
- TM computing f(n) = n + 1 · Theory of Computation, chapter 4
- Random process; LTI output is WSS if input is WSS · Communication Systems, chapter 9
- Data logger input scanner and conditioner design · Instrumentation II, chapter 5
- Sallen-Key LPF at 10 kHz, largest C 0.01 μF · Filter Design, chapter 6
- Should technicians also be good citizens · Communication English, chapter 2 · asked 2×