-
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$
-
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$
-
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}\}$