PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q4(b)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

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:

  1. Start in state at the leftmost bit of the input.
  2. When reading 0, overwrite with 1 and move tape head Right ().
  3. When reading 1, overwrite with 0 and move tape head Right ().
  4. When reading blank (end of input), transition to accepting halt state with head stationary ().

Formal Machine Specification:

TM: Binary Complement TransducerTM
TM: Binary Complement Transducer 0/1,R 1/0,R B/B,S q0 q_done
StateReadNext StateWriteMove
→q00q01R
→q01q00R
→q0Bq_doneBS
  • 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 .

All past exam questions for Theory of Computation