where
Chapter 9: Turing Machines and Linear Bounded Automata I!O! 287
Keeping these ideas in our mind, we construct a TM M as follows:
M = (Q, L, r, 0, qo, b, F)
Q = {qo, qj, q2' q3' qt)
F = {qt}
L = {O, I}
r = {O, 1, x, y, b}
The transition diagram is given in Fig. 9.7. M accepts {0
11 1
11
1n ;:::: I}. The moves
for 0011 and 010 are given below just to familiarize the moves of M to the
reader.
(0,0, R)
(y, y, R)
(x, x, R)
(y,y, R)
(y, Y, L)
(0,0, L)
Transition diagram for Example 9.7.
+
rt:::\
(b, b, R)
f0.,
(y, Y, R) ~f-----------I'~
Fig. 9.7
q o 0011 r- xq j 011j- xOq j 11 1- xq20yl
r- q2xOy 1 1- xq o Oy 1 1- xxqjy1 1- xxyq j l
r- xxq2..1')' r- xChJ:YY r- xxqoYy r- x·\yq3Y
r- :'oyyq3 = xxyyq3 b r- xxyybq.<,b
Hence 0011 is accepted by M.
q o OlO r- xq j lO r- q2·rvO r- xqayO r- xyq30
As 0(Q3' 0) is not defined, M halts. So 010 is not accepted by M.
·-EXAMPLE 9.8
Design a Turing machine M to recognize the language
{1"2"3"ln ;:::: I}.