44 FINITE AUTOMATA
Figure 2.25: Kleene closure of an NFA.
final state f ( so that the empty string E is accepted). This NFA IV is shown
in Figure 2.25. Note that the new initial and final states are necessary. See
Exercise 4 of this section for counterexamples.^0
Exercise 2.3
- Consider the NFA IV of Figure 2.26.
1
c) & 0
0 1 5(^1) E E
1 1
[
0
(^2 0)
0
3 0 4
&
Figure 2.26: The NFA of Exercise 1.
(a) What are E-closure( { Qo}) and E-closure( { q1, q2, qs})?
(b) What are S({qo}, 0) and 6({q2, qij, l)?
(c) Draw the computation trees of AI on strings x = 011 and y = 101.
Does AI accept or reject x and y?
- For each NFA M shown in Figure 2.27, determine what L(M) is.
- For each of the following languages, construct an NFA that accepts the
language:
(a) The set of binary strings that contain at least three occurrences
of substring 010.
(b) The set of binary strings that contain both substrings 010 and- [Hint: This is equivalent to the set of binary strings that
contain either a substring 0101 or a substring 1010 or a substring
010 followed by 101 or a substring 101 followed by OlO.]