Past exam question: 2082 Chaitra (Regular), Q12(b)
Open in the Padhaiko appQuestion
Design a Turing machine which reverses the given string over alphabet .
Solution
Reversal Algorithm Specification: We design a deterministic Turing Machine transducer that replaces input string on the tape with its reverse :
Algorithm:
- If tape is empty (), halt immediately (reverse of is ).
- Scan right across input to the first blank and append delimiter marker
D. - Sweep left to locate the rightmost unmarked symbol ( or ) of the original string. Mark it ( or ).
- Carry that symbol rightward past delimiter
Dand any previously written output symbols, appending it onto the next available blank cell. - Return left past
Dto find the next unmarked symbol and repeat. - When all symbols of the original string have been marked ( and only), move right to erase all 's, 's, and delimiter
D(overwriting with blank ), leaving only the reversed string on the tape.
Formal Automaton Implementation: The formal machine specification and transitions are:
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | B | q_done | B | S |
| →q0 | a | q_scan | a | R |
| →q0 | b | q_scan | b | R |
| q_scan | a | q_scan | a | R |
| q_scan | b | q_scan | b | R |
| q_scan | B | q_find_right | D | L |
| q_find_right | X | q_find_right | X | L |
| q_find_right | Y | q_find_right | Y | L |
| q_find_right | a | q_write_a | X | R |
| q_find_right | b | q_write_b | Y | R |
| q_find_right | B | q_clean | B | R |
| q_write_a | X | q_write_a | X | R |
| q_write_a | Y | q_write_a | Y | R |
| q_write_a | D | q_write_a | D | R |
| q_write_a | a | q_write_a | a | R |
| q_write_a | b | q_write_a | b | R |
| q_write_a | B | q_back | a | L |
| q_write_b | X | q_write_b | X | R |
| q_write_b | Y | q_write_b | Y | R |
| q_write_b | D | q_write_b | D | R |
| q_write_b | a | q_write_b | a | R |
| q_write_b | b | q_write_b | b | R |
| q_write_b | B | q_back | b | L |
| q_back | a | q_back | a | L |
| q_back | b | q_back | b | L |
| q_back | D | q_back | D | L |
| q_back | X | q_find_right | X | L |
| q_back | Y | q_find_right | Y | L |
| q_clean | X | q_clean | B | R |
| q_clean | Y | q_clean | B | R |
| q_clean | D | q_done | B | R |
- Machine-checked
- ✓ ab → ba
- ✓ ba → ab
- ✓ aab → baa
- ✓ aba → aba
- ✓ bba → abb
Answer:
The TM appends delimiter , iteratively marks the rightmost available symbol of (), copies it to the output region after , and finally erases the original marked symbols and delimiter to leave on the tape.