2.3 Nondeterministic Finite Automata 43
(a)(b)0(^0 0)
1 1 1 1 1
? t t? 7
0
0 0
(^1 1 1 1 1)
0 0 0 0
0
0 0 0 0
Figure 2.23: Solution to Example 2.20.
Figure 2.24: Concatenation of two NFA’s.
the set F of the final states of M be equal to I$ We also add an E-move from
each state Q in F1 to the initial state 402 of M 2. We show the construction in
Figure 2.24. For convenience, we only show one final state for each of Ml and
M2 cl
Example 2.22 Let Ml be an NFA. Construct an NFA M such that L(M) =
L(m) *
Solution. Let Ml = (&I, C, 61, ~0, Fl) be an NFA. We construct M by adding
a new initial state s and a unique final state f. Then, we add an E-move from
s to the initial state 40 of Ml and an E-move from each qi E Fl to the new
final state f. We also add, from each state qi E Fl, an E-move to the initial
state qo of Ml. Finally, we add an E-move from the initial state s to the new