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

 modified 3.0 years ago  • written 3.0 years ago by Pooja Joshi • 740
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.

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