Formal Language and Automata Homework 11 Answer

       

  1. Show the ID’s of the Turing machine of Fig. 8.9 if the input tape contains:

    a) $00$.

    $q_000 \vdash Xq_10 \vdash X0q_1B$

    b) $000111$​. (답안이 길어 표로 작성함.)

    $q_0000111 $ $Xq_100111$ $X0q_10111 $ $X00q_1111 $ $X0q20Y11 $ $q_2X00Y11 $
    $Xq_000Y11$ $XXq_10Y11$ $XX0q_1Y11 $ $XX0Yq_111 $ $XX0q_2YY1$ $XXq_20YY1$
    $Xq_2X0YY1$ $XXq_00YY1$ $XXXq_1YY1 $ $XXXYq_1Y1 $ $XXXYYq_11$ $XXXYq_2YY $
    $XXXq_2YYY$ $XXq_2XYYY $ $XXXq_0YYY $ $XXXYq_3YY $ $XXXYYq_3Y $ $XXXYYYq_3B$
    $XXXYYYBq_4B$          

    c) $00111$.

    $q_000111 \vdash Xq_10111 \vdash X0q_1111 \vdash Xq_20Y11 \vdash q_2X0Y11 \vdash Xq_00Y11 \vdash XXq_1Y11 \vdash $$XXYq_111 \vdash XXq_2YY1 \vdash Xq_2XYY1 \vdash XXq_0YY1 \vdash XXYq_3Y1 \vdash XXYYq_31$

   

  1. Design Turing machines for the following languages:

    a) The set of strings with an equal number of $0$’s and $1$’s.

    TM $M_1 = (Q,\Sigma,\Gamma,\delta,q_0,q_0,r)$:

    $Q = {\{q_0,q_1,q_2,q_3}\}$

    $\Sigma = {\{0,1}\}$

    $\Gamma = {\{0,1,X,B}\}$

    $\delta$ contains:

      0 1 X B
    $q_0$ $(q_1,B,R)$ $(q_3,B,R)$ $(q_0,B,R)$  
    $q_1$ $(q_1,0,R)$ $(q_2,X,L)$ $(q_1,X,R)$  
    $q_2$ $(q_2,0,L)$ $(q_2,1,L)$ $(q_2,X,L)$ $(q_0,B,R)$
    $q_3$ $(q_2,X,L)$ $(q_3,1,R)$ $(q_3,X,R)$  

    b) ${\{a^n b^n c^n \mid n\ge 1}\}$.

    TM $M_2 = (Q,\Sigma,\Gamma,\delta,q_0,f,r)$:

    $Q = {\{q_0,q_1,q_2,q_3,q_4,f}\}$

    $\Sigma = {\{0,1}\}$

    $\Gamma = {\{0,1,2,X,Y,Z,B}\}$

    $\delta$ contains:

      0 1 2 X Y Z B
    $q_0$ $(q_1,X,R)$       $(q_4,Y,R)$    
    $q_1$ $(q_1,0,R)$ $(q_2,Y,R)$     $(q_1,Y,R)$    
    $q_2$   $(q_2,1,R)$ $(q_3,Z,R)$     $(q_2,Z,R)$  
    $q_3$ $(q_3,0,L)$ $(q_3,1,L)$   $(q_0,X,R)$ $(q_3,Y,L)$ $(q_3,Z,L)$  
    $q_4$         $(q_4,Y,R)$ $(q_4,Z,R)$ $(f,B,L)$
    $f$              

    c) ${\{ww^R \mid w}$ is any string of $0$’s and $1$’s${}\}$.

    TM $M_3 = (Q,\Sigma,\Gamma,\delta,q_0,f,r)$:

    $Q = {\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,f}\}$

    $\Sigma = {\{0,1}\}$

    $\Gamma = {\{0,1,X,Y,B}\}$

    $\delta$ contains:

      0 1 X Y B
    $q_0$ $(q_2,Y,R)$ $(q_1,X,R)$ $(q_6,X,R)$ $(q_6,Y,R)$  
    $q_1$ $(q_1,0,R)$ $(q_1,1,R)$ $(q_3,X,L)$ $(q_3,Y,L)$ $(q_3,B,L)$
    $q_2$ $(q_2,0,R)$ $(q_2,1,R)$ $(q_3,X,L)$ $(q_3,Y,L)$ $(q_3,B,L)$
    $q_3$ $(q_5,Y,L)$ $(q_4,X,L)$      
    $q_4$ $(q_4,0,L)$ $(q_4,1,L)$ $(q_0,X,R)$ $(q_0,Y,R)$  
    $q_5$ $(q_5,0,L)$ $(q_5,1,L)$ $(q_0,X,R)$ $(q_0,Y,R)$  
    $q_6$     $(q_6,X,R)$ $(q_6,Y,R)$ $(f,B,L)$
    $f$          

   

  1. Consider the Turing machine

    $M=({\{q_0,q_1,q_2,q_f}\},{\{0,1}\},{\{0,1,B}\},\delta,q_0,B,{\{q_f}\})$

    Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules:

​ a) $\delta(q_0,0)=(q_1,1,R);\delta(q_1,1)=(q_0,0,R);\delta(q_1,B)=(q_f,B,R)$.

​ $L = {\{ (01)^n0 \mid n \geq 0}\}$

​ b) $\delta(q_0,0)=(q_0,B,R);\delta(q_0,1)=(q_1,B,R);\delta(q_1,1)=(q_1,B,R);\delta(q_1,B)=(q_f,B,R)$

​ $L = {\{ 0^n1^m \mid n \geq 0, m \geq 1}\}$

​ c) $\delta(q_0,0)=(q_1,1,R);\delta(q_1,1)=(q_2,0,L);\delta(q_2,1)=(q_0,1,R);\delta(q_1,B)=(q_f,B,R)$

​ $L = {\{ 01^n \mid n \geq 0}\}$