Last updated on:May 26th, 2018,

Turing Machine for complement of a string in Theory Of Automata

Turing Machine for the complement of a string:

Turing Machine in the diagram 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, than 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 delta because in the rightmost, always input tape have a delta or can have some other variable instead 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

0Shares

Leave a Reply

Your email address will not be published.