Computer Science, asked by sjkbheltry, 10 days ago

Construct Turning Machine .That replace all occurrence of 111 by 101 from sequence of 0' and 1's

Answers

Answered by singhbhadoriatanay
0

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

Similar questions