1. Use the construction of Theorem 2.2 to convert the nfa in Figure 2.10 to a
dfa. Can you see a simpler answer more directly?
2. Convert the nfa in Exercise 12, Section 2.2, into an equivalent dfa.
3. Convert the following nfa into an equivalent dfa.
4. Carefully complete the arguments in the proof of Theorem 2.2. Show in detail
that if the label of
contains q f , then
also contains q f .
5. Is it true that for any nfa M = (Q,Σ,δ,q 0 ,F) the complement of L(M)is equal to
the set {w ∈ Σ * : δ * (q 0 ,w) F= Ø}? If so, prove it. If not, give a
counterexample.
6. Is it true that for every nfa M = (Q, Σ,δ,q 0 ,F)the complement of L (M)is equal
to the set {w ∈ Σ * : δ * ; (q 0 ,w) ∈ (Q – F) = Ø}? If so, prove it; if not, give a
counterexample.
7. Prove tha for every nfa with an arbitrary number of final states there is an
equivalent nfa with only one final state. Can we make a similar claim for
8. Find an nfa without λ-transitions and with a single final state that accepts the
set {a}∪{b n : n ≥1}.
9. Let L be a regular language that does not contain λ. Show that there exists an
nfa without λ-transitions and with a single final state that accepts L.
10. Define a dfa with multiple initial states in an analogous way to the
corresponding nfa in Exercise 18, Section 2.2. Does there always exist an
equivalent dfa with a single initial state?
11. Prove that all finite languages are regular.
12. Show that if L is regular, so is L R .
13. Give a simple verbal description of the language accepted by the dfa in
Figure 2.16. Use this to find another dfa, equivalent to the given one, but
with fewer states.
* 14. Let L be any language. Define even (w) as the string obtained by extracting