Question

Construct Turing machine (TM) that replace all occurrence of 111 by 101

from sequence of 0’s and 1’s.​

Answer 1

Answer:

this is a question of maths or other subject

Answer 2

Answer:

• The Turing machine will look for every occurrence of the string 110.

• Look at the Picture that has been given as attachment.

        State $q_{2}$ is depicting  previous two symbols as 11.

        Next symbol as 0 in state $q_{2}$  will initiate the replacement process

        and will replace 110 by 101.

• The Turing machine M is given by the followings:

       M=(Q,Σ,Ґ,δ,q0,B,F), where

       Q=$q_{0}$, $q_{1}$, $q_{2}$, $q_{3}$,$q_{4}$,$q_{5}$

       Σ=0,1

       Ґ=0,1,B

       δ=Transition function is shown using the transition diagram\.f

       B=Blank symbol for the tape . F=$q_{5}$, halting state.

• Working of the machine for input 01011101 is shown in fig below:

0101101 B |- 0101101 |- 0101101 B |- 0101101

                                                                        $q_{0} q_{0} q_{1} q_{0}$

0101101 B |- 0101101

                                                                          $q_{1} q_{2}$

0101111 B |- 0101101 B

                                                                          $q_{3}q_{4}$

0101101 B |- 010111B |- 0101101 B

                                                                       $q_{0} q_{1} q_{5}$(halt)