306 J;I, Theory of Computer Science
TABLE 9.12 Transition Table for Example 9.16
Present state
Tape symbol
0
b
.r
qo
bRq1
bRqt
xRqt
q1
.rRq2
bRqf
xRq1
q2
ORq3
bRq4
xRq2
q3
xRq2
bRq6
xRq3
q4
OLQ4
bRQ1
xLQ4
Qr
Qt
From the construction, it is apparent that the states are used to know
whether the number of O's read is odd or even.
We can see how M processes 0000.
qoOOOO ~ bCf1000 ~ bJ.(1200 ~ b.xxl30 ~ bX{)XCf2b
~ bxOq.+xb ~ bxq.+Oxb ~ bq4--r:Oxb ~ q4bxOxb
~ bq1xO.-r:b ~ bxq10xb ~ bx.-r:Cf2Xb ~ bxxxq2b
~ bxxq4xb ~ bxq.+xxb ~ bqJ,xxxb ~ qJ,bxxxb
~ bqlxxxb ~ bXqlxxb ~ bxxqjxb ~ bxxxqjb
~ bxxxbCfI'
Hence M accepts \i'.
Also note that M always halts. If M reaches qt, the input stling 11' is
accepted by M. If M reaches qr- }t' is not accepted by M; in this case M halts
in the trap state.
EXAMPLE 9.17
Let M = ({qo, qj, q2}. {O. I}. {O, 1, b}. 8, qo, {q2})
where 8 is given by
8(qo, 0) = (qj, 1, R)
8(qj, 1) = (qo- 0, R)
8(qj. b) =(q2' b, R)
(R j )
(R 2 )
(R 3 )
Find T(M),
Solution
Let 11' E T(M), As 8(qo, 1) is not defined, w cannot start with 1. From (Rd
and (R 2 ), we can conclude that M starts from qo and comes back to Cfo after
reaching 01.
So. qo(OI)" f-2- (lO)"qo· Also, qoOb ~ lq]b ~ Ibq2'