Turing Machine for complement of a string in Theory Of Automata

By: Prof. Fazal Rehman Shamil
Last modified on January 25th, 2021

Turing Machine for the complement of a string

Turing Machine in the machine that can convert every 1 to 0 and every 0 to 1.

1. First of all, start the machine.

If there is any 0 on input tape than machine read 0 and write 1.

If there is any 1 on input tape than machine read 1 and write 0.

2. On state 2, there is a loop of;

If there is any 0 on input tape, then machine read 0 and write 1.

If there is any 1 on input tape than machine read 1 and write 0.

3. On state 2, there is a transition of the delta because in the rightmost, always input tape has a delta or can have some other variable instead of the delta.

Accept is the final state where machine halts by successfully accepting the string.

turing machine to makes every a as b and every b to a

Figure: Turing Machine to makes every 1 as o and every 0 to 1

Example of Turing Machine for the complement of a string

Suppose the string is 0101101.

Question: How a Turing machine can convert this into its complement?

The path will be looks like;

Path: Start  2 > 2 > 2 > 2 > 2 > 2 > 2 > accept

After the complement, the string will be looks like;

1010010

String before Complement String after Complement
0101101 1010010

Read More Examples of Turing Machine

  1. Turing Machine to copy a string: with animations
  2. Turing Machine of numbers divisible by 3: with animations
  3. Turing machine for anbncn: with animations
  4. Turing machine of two equal binary strings: with animations

  5. Turing Machine to Accepts palindromes: with animations

  6. Turing machine for a’s followed by b’s then c’s where the number of a’s multiplied by the number of b’s and equals to the number of c’s: with animations

  7. Turing machine to Add two binary numbers: with animations

  8. Turing machine to  Multiply two unary numbers: with animations
  9. Turing machine to Multiply two binary numbers: with animations
  10. Turing Machine for the complement of a string
  11. Turing Machine for the language of anbn where a=b.
  12. Turing Machine for a is less than b, ambn where a=b or m=n.
  13. Turing machine for the language of all those string in which a is less than b