Table of Contents
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 |
