Problem Solving in Automata, Languages, and Complexity

46 FINITE AUTOMATA

(a) NFA Ml' (b) NFA M2'

Figure 2.28: Two attempts for Kleene closures of NFA’s.

To see how to do this conversion, let us consider an NFA A4 =
(Q, C,S, 40, F). For any x E C, let Qz be the set of states which are the
end states of the computation paths of x in M; that is, QI = S( {QO}, x),
where S is the extended transition function defined on 2Q x C. In par-
ticular, QE = E-closure( { ao}). Th en, x is accepted by M if and only if
Qz n F # 8. Thus, it suggests that we can use these subsets Qz C Q as
the states for the equivalent DFA. In other words, we would like to construct
a DFA M’ = (Q’, C, S’, QE, F’) with the following properties:

Q

/

= {Qx 1 ~xf E c*},

Ff = i&x I Qx n F # 0},

S/(&x+) = Qxa, for x: E C*, a E Sigma.

Note that each Qz is a subset of Q, and so Q’ is a finite set. Indeed, Q’ C 2Q
and so IQ’1 < 2 IQI. Furthermore, if Qz = QY, then Qza = QYa for all a2 C.
It follows that the above definition of 6’ is well defined. In fact, using the
extended transition function S of M, we know that for any x E C* and a E C,
J’(Qx > a) = S(Qx, a). The above analysis shows that this construction is
feasible. We call it the subset construction for DFA’s. The following are some
examples.

Example 2.23 An NFA M = (Q, (0, l},S, qo, F) is given by Q = {qo, ql, 42,

q3,q4, q5}, F = 143, q4lr m-d

s 0 1 E

40 {Qo) -ho7 !d (Q11

41 {Qd (ad -

42 {cl31 - -

q3 - - Gil 1

q4 {43) - _”

45 - hl 4 I -

(See Figure 2.29(a) for the transition diagram of M .) Find a DFA which is

equivalent to the NFA M.