Past exam question: 2082 Kartik (Back), Q4(b)
Open in the Padhaiko appQuestion
Design a Turing machine that can generate the complement of the binary string.
Solution
Transducer Algorithm and Formulation: The complement of a binary string is obtained by inverting each bit: replacing every 0 with 1 and every 1 with 0 (bitwise NOT operation).
Operational Logic:
- Start in state at the leftmost bit of the input.
- When reading
0, overwrite with1and move tape head Right (). - When reading
1, overwrite with0and move tape head Right (). - When reading blank (end of input), transition to accepting halt state with head stationary ().
Formal Machine Specification:
- Transitions:
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 1 | R |
| →q0 | 1 | q0 | 0 | R |
| →q0 | B | q_done | B | S |
- Machine-checked
- ✓ 0 → 1
- ✓ 1 → 0
- ✓ 101 → 010
- ✓ 000 → 111
- ✓ 1101 → 0010
Answer:
A 2-state TM transducer scans left-to-right, replacing each 0 with 1 and each 1 with 0, halting in state upon encountering blank .