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.

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

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 aⁿbⁿ where a=b.
12. Turing Machine for a is less than b, a^mbⁿ where a=b or m=n.

13. Turing machine for the language of all those string in which a is less than b

     

• Author
• Recent Posts

Prof. Fazal Rehman Shamil

 CEO @ T4Tutorials.com
I welcome to all of you if you want to discuss about any topic. Researchers, teachers and students are allowed to use the content for non commercial offline purpose. Further, You must use the reference of the website, if you want to use the partial content for research purpose.

Latest posts by Prof. Fazal Rehman Shamil (see all)

• 5 Best Places to Study Engineering - March 19, 2021
• How Students Can Pick a Good Custom-Paper Writing Service? - March 5, 2021
• List of Public service commissions - August 31, 2020