(b) Do you think the language in part (a) can be accepted by an nfa with
fewer than three states?
11. Find an nfa with four states for L= {a n : n ≥ 0}∪{b n a: n ≥ 1}.
12. Which of the strings 00, 01001, 10010, 000, 0000 are accepted by the
following nfa?
13. What is the complement of the language accepted by the nfa in Figure 2.10?
14. Let L be the language accepted by the nfa in Figure 2.8. Find an nfa that
accepts L ∪ {a 5 }.
15. Give a simple description of the language in Exercise 13.
16. Find an nfa that accepts { a} * and is such that if in its transition graph a
single edge is removed (without any other changes), the resulting automaton
accepts {a}.
17. Can Exercise 16 be solved using a dfa? If so, give the solution; if not, give
convincing arguments for your conclusion.
18. Consider the following modification of Definition 2.6. An nfa with multiple
initialstates is defined by the quintuple
M =(Q, Σ,δ,q 0 ,F),
where Q 0 ⊆ Q is a set of possible initial states. The language accepted by
such an automaton is defined as
L (M)= {w :δ *(q 0 ,w) contains q f , for any q 0 ∈ Q 0 ,q f ∈ F}.
Show that for every nfa with multiple initial states there exists an nfa with a
single initial state that accepts the same language.
19. Suppose that in Exercise 18 we made the restriction Q 0 F= Ø. Would this
affect the conclusion?
fewer than three states?
11. Find an nfa with four states for L= {a n : n ≥ 0}∪{b n a: n ≥ 1}.
12. Which of the strings 00, 01001, 10010, 000, 0000 are accepted by the
following nfa?
13. What is the complement of the language accepted by the nfa in Figure 2.10?
14. Let L be the language accepted by the nfa in Figure 2.8. Find an nfa that
accepts L ∪ {a 5 }.
15. Give a simple description of the language in Exercise 13.
16. Find an nfa that accepts { a} * and is such that if in its transition graph a
single edge is removed (without any other changes), the resulting automaton
accepts {a}.
17. Can Exercise 16 be solved using a dfa? If so, give the solution; if not, give
convincing arguments for your conclusion.
18. Consider the following modification of Definition 2.6. An nfa with multiple
initialstates is defined by the quintuple
M =(Q, Σ,δ,q 0 ,F),
where Q 0 ⊆ Q is a set of possible initial states. The language accepted by
such an automaton is defined as
L (M)= {w :δ *(q 0 ,w) contains q f , for any q 0 ∈ Q 0 ,q f ∈ F}.
Show that for every nfa with multiple initial states there exists an nfa with a
single initial state that accepts the same language.
19. Suppose that in Exercise 18 we made the restriction Q 0 F= Ø. Would this
affect the conclusion?