In the same vein, nondeterminism is an effective mechanism for describing
some complicated languages concisely. Notice that the definition of a grammar
involves a nondeterministic element. In we can at any point choose either the
first or the second production. This lets us specify many different strings using
only two rules.
S → aSb|λ
Finally, there is a technical reason for introducing nondeterminism. As we
will see, certain theoretical results are more easily established for nfa's than for
dfa's. Our next major result indicates that there is no essential difference between
these two types of automata. Consequently, allowing nondeterminism often
simplifies formal arguments without affecting the generality of the conclusion.
EXERCISES
1. Prove in detail the claim made in the previous section that if in a transition
graph there is a walk labeled w, there must be some walk labeled w of length
no more than Λ + (1 + Λ) |w|.
2. Find a dfa that accepts the language defined by the nfa in Figure 2.8.
3. Find a dfa that accepts the complement of the language defined by the nfa in
Figure 2.8.
4. In Figure 2.9, find δ * (q 0 ,1011) and δ * (q 1 ,01).
5. In Figure 2.10, find δ * (q 0 , a)and δ * ( q 1 ,λ).
6. For the nfa in Figure 2.9, find δ * (q 0 , 1010) and δ * (q 1 ,00).
7. Design an nfa with no more than five states for the set {abab n : n >0}∪{aba n :
n ≥ 0}.
8. Construct an nfa with three states that accepts the language {ab,abc} * .
9. Do you think Exercise 8 can be solved with fewer than three states?
10.(a) Find an nfa with three states that accepts the language
some complicated languages concisely. Notice that the definition of a grammar
involves a nondeterministic element. In we can at any point choose either the
first or the second production. This lets us specify many different strings using
only two rules.
S → aSb|λ
Finally, there is a technical reason for introducing nondeterminism. As we
will see, certain theoretical results are more easily established for nfa's than for
dfa's. Our next major result indicates that there is no essential difference between
these two types of automata. Consequently, allowing nondeterminism often
simplifies formal arguments without affecting the generality of the conclusion.
EXERCISES
1. Prove in detail the claim made in the previous section that if in a transition
graph there is a walk labeled w, there must be some walk labeled w of length
no more than Λ + (1 + Λ) |w|.
2. Find a dfa that accepts the language defined by the nfa in Figure 2.8.
3. Find a dfa that accepts the complement of the language defined by the nfa in
Figure 2.8.
4. In Figure 2.9, find δ * (q 0 ,1011) and δ * (q 1 ,01).
5. In Figure 2.10, find δ * (q 0 , a)and δ * ( q 1 ,λ).
6. For the nfa in Figure 2.9, find δ * (q 0 , 1010) and δ * (q 1 ,00).
7. Design an nfa with no more than five states for the set {abab n : n >0}∪{aba n :
n ≥ 0}.
8. Construct an nfa with three states that accepts the language {ab,abc} * .
9. Do you think Exercise 8 can be solved with fewer than three states?
10.(a) Find an nfa with three states that accepts the language