Construct Turning Machine .That replace all occurrence of 111 by 101 from sequence of 0' and 1's
Answers
Explanation:
The turing machine will look for every occurrence of the string 110.
State q_2 is for previous two symbols as 11.
Next symbol as 0 in stateq2stateq2, will initiate the replacement process to replace 110 by 101.

The turing machine M is given by:
M=(Q,Σ,Ґ,δ,q0,B,F)M=(Q,Σ,Ґ,δ,q0,B,F)
Q=q0,q1,q2,q3,q4,q5Q=q0,q1,q2,q3,q4,q5
Σ=0,1Σ=0,1
Ґ=0,1,BҐ=0,1,B
δ=Transition function is shown using the transition diagram\.fδ=Transition function is shown using the transition diagram\.f
B=Blank symbol for the tapeB=Blank symbol for the tape . F=q5F=q5, halting state.
Working of the machine for input 01011101 is shown in fig below:
0101101 B |- 0101101 |- 0101101 B |- 0101101
q0q0q1q0q0q0q1q0
0101101 B |- 0101101
q1q2q1q2
0101111 B |- 0101101 B
q3
The turing machine will look for every occurrence of the string 110.
State q_2 is for previous two symbols as 11.
Next symbol as 0 in stateq2stateq2, will initiate the replacement process to replace 110 by 101.

The turing machine M is given by:
M=(Q,Σ,Ґ,δ,q0,B,F)M=(Q,Σ,Ґ,δ,q0,B,F)
Q=q0,q1,q2,q3,q4,q5Q=q0,q1,q2,q3,q4,q5
Σ=0,1Σ=0,1
Ґ=0,1,BҐ=0,1,B
δ=Transition function is shown using the transition diagram\.fδ=Transition function is shown using the transition diagram\.f
B=Blank symbol for the tapeB=Blank symbol for the tape . F=q5F=q5, halting state.
Working of the machine for input 01011101 is shown in fig below:
0101101 B |- 0101101 |- 0101101 B |- 0101101
q0q0q1q0q0q0q1q0
0101101 B |- 0101101
q1q2q1q2
0101111 B |- 0101101 B
q3