Automata

Turing machine as transducer for 2's complement

Approach for 2's complement

  1. Scan input string from right to left
  2. Pass all consecutive '0's
  3. When '1' comes do nothing
  4. After that take complement of every digit.
Overflow is not taken care in this approach

TAPE movement for string "1010100":


Explanation of TAPE movement

  1. Input is given as "1010100" (scan string from right to left)
  2. Pass two '0's from right
  3. Pass '1' after that
  4. Take complement of '0' = '1'
  5. Take complement of '1' = '0'
  6. Take complement of '0' = '1'
  7. Take complement of '1' = '0'
  8. BLANK(in left) is reached when string is finished. So move to start of string(optional) by moving one step right.
2's complement is written into the TAPE in place of input string.
Input String : 1010100
Output String : 0101100

State Transition Diagram

We have designed state transition diagram for 2's complement as follows:
1. Go to right of string using state q0
2. When BLANK is reached take one step left
3. Start scanning string from right to left
4. Pass all '0's and keep moving left
5. Pass single '1' and move left
6. Take complement of '1' and '0' after that.
7. When BLANK(in left) is reached move one step right and point to start of string.