Chapter 9: Turing Machines and Linear Bounded Automata J;! 307
So, (On"O E T(M). Also, (OltO is the only string that makes M move from
qo to Cf~· Hence, T(M) = {(Olto In;:: O}.
SELF-TEST
Choose the correct answer to Questions 1-10:
1. For the standard TM:
(a) L =r
(b) r <;:;;; L
(c) L <;:;;; r
(d) L is a proper subset of r.
2. In a standard TM. D(q. a), q E Q, a E r is
(a) defined for all (q. a) E Q x r
(b) defined for some. not necessarily for all (q, a) E Q x r
(c) defined for no element (q. a) of Q >< r
(d) a set of triples with more than one element.
3. If D(q. .\J = (p. Y. I), then
(a) XlX~
Xi-lqxi
x" ~ XIX2
xi_~pxi_l.vxi+l ... .en
(b) XIX~
xi_lqxi
x" ~ Xl.Y2
'Yi-lYi'JXi+I ... x"
(c) XIX~
xi_IqXi
XI) ~ XI
·'(i-3P.Yi-~Xi-1YXi+l ... XII
(d) XIX~
xi-lqxi
XII ~ XI
Xi+J1T\'Xi+~ ... X n
4. If D(q. X;) =(p. y. R). then
(a) XIX~
'Yi-lqxi
Xii ~ XIX~
Xi-lypXi+l
x"
(b) X1X~
xi-lqxi
Xli ~ X)X2
XiPXi+l
.1'1/
(e) X,X2
xi-lq'Yi
X" ~ X)'Y2
Xi-1PXiXi+l
x"
(d) X!X~
Xi-1CfXi
X1/ ~ .1'1"2
Xi-lypXi+J
X1/
5. If D(q. Xl) = (p, y. I). then
(a) qXlx~
Xii ~ p.vX~
Xli
(b) q.YIX~
X" ~ yp.Y~
Xli
(e) qXJX~
X" ~ pbx]
X I1
(d) qx(r~
X" ~ pbx~
x"
6. If D(q. x l1
) = (v. Y. R). then
(a) Xl ... x n _lqx" ~ PYX2J:3
X n
(b) x • ... X1/-1q·\, p:- PYX~X3
XII
(c) Xl
x n _lqx l1 ~ XIX~
X"_l)pb
(d) Xl
X"_lqx,, p:- XIX~
xn_lypb
7. For the TM given in Example 9.6:
(a) qolbll p:- bq j llbbl
(b) qn lbll i- bqrllbhl
(c) Cj(Jlbll ~ lqoblll
(d) Cjolbll ~ (j3bllbbl