82 g Theory of Computer Science
TABLE 3.2 State Table for Example 3,6
State/L
o
~@
qo
q,
_ _--' qC-' -'
q--' i
qo, ql
Solution
For the deterministic automaton MI.
(i) the states are subsets of {qo. Ql}, i.e. 0. [qo], [c/o' q;], [q;];
(ii) [qoJ is the initial state;
(iii) [qo] and [qo, q;] are the final states as these are the only states
containing qo; and
(iv) 8 is defined by the state table given by Table 3.3.
TABLE 3.3 State Table of M , for Example 3,6
State/'L
o
[qo]
[q,]
[qo, q,]
o
o
[qo]
[q,]
[qo, q,]
o
[q,]
[qo, q,]
[qo, q,]
The states qo and ql appear in the rows corresponding to qo and qj and the
column corresponding to O. So. 8([qo. qt], 0) = [qo. qd·
When M has 11 states. the corresponding finite automaton has 2" states.
However. we need not construct 8 for all these 2" states, but only for those
states that are reachable from [Qo]. This is because our interest is only in
constructing M 1 accepting T(M). So, we start the construction of 8 for [qo]. We
continue by considering only the states appearing earlier under the input
columns and constructing 8 for such states. We halt when no more new states
appear under the input columns.
EXAMPLE 3.7
Find a detefIIljnistic acceptor equivalent to
M = ({qo. qIo q:J. {a. hI. 8. qo. {q2})
where 8 is as given by Table 3.4.
TABLE 3.4 State Table for Example 3.7
State/'L
a
b
~qo
qo. q,
q2
q,
qo
q,
@
qo. q,