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.
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 |
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.
- List of Public service commissions - August 31, 2020
- Comparison of fee structure of Pakistani Universities - June 1, 2020
- Past Guess Paper of Auditing - May 12, 2020