Automata

Turing machine as transducer for 1's complement

Turing machine can work as Transducer as well as Acceptor.

Transducer

When input is converted into output.

Acceptor

When it is decided that whether string belongs to language or not.(Answer in YES or NO). Example: DFA, PDA etc

Turing machine can read as well as write on the TAPE that is the reason it can work as TRANSDUCER.

Approach for 1's complement

  1. Scan input string from left to right
  2. Convert '1' into '0'
  3. Convert '0' into '1'
  4. When BLANK is reached move towards left(start of input string).

TAPE movement for string "1010111":


Explanation of TAPE movement

  1. Input is given as "1010111" (scan string from left to right)
  2. Convert '1' into '0' and move one step right
  3. Convert '0' into '1' and move one step right
  4. Convert '1' into '0' and move one step right
  5. Convert '0' into '1' and move one step right
  6. Convert '1' into '0' and move one step right
  7. Convert '1' into '0' and move one step right
  8. Convert '1' into '0' and move one step right
  9. BLANK(in right) is reached when string is finished. So move to start of string(optional).
1's complement is written into the TAPE in place of input string.
Input String : 1010111
Output String : 0101000

State Transition Diagram

We have designed state transition diagram for 1's complement as follows:
1. Replace '1' with '0' and vice versa.
2. When BLANK is reached move towards left
3. Using state 'q2' we reach start of the string.
4. When we reach BLANK in left we move one step right to point start of string.
5. qf is final state




Quantitative Aptitude
Reasoning
Programming
Interview