• 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 $stateq_2$, will initiate the replacement process to replace 110 by 101.

• The turing machine M is given by:

  $M = (Q, Σ, Ґ, δ,q_0, B, F )$

  $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)$$