Question: Construct Turing machine that accepts the string over E={0,1} and converts every occurrence of 111 to 101.
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2015

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
0
  • 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.

enter image description here

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

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.