Non-Deterministic Finite Automata

1. Construct an nfa that accepts all integer numbers in C. Explain why your construct is an nfa.

2. 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|.

3. Find a dfa that accepts the language defined by the nfa in Figure 2.8.

4. Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.

5. Convert the nfa defined by

δ(q0,a)δ(q1,b)δ(q2,a)==={q0,q1}{q1,q2}{q2}δ(q0,a)={q0,q1}δ(q1,b)={q1,q2}δ(q2,a)={q2}

with initial state q0 and final state q2 into an equivalent dfa.

6. Is it true that for every nfa M = (Q, Σ, δ, q0, F), the complement of L (M) is equal to the set {w ∈ Σ* : δ*

(q0, w) ∩ (Q − F) ≠ ∅}? If so, prove it; if not, give a counterexample.

7. Prove that 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 dfa’s?

8. Consider the dfa with initial state q0, final state q2 and δ(q0,a)=q2δ(q1,a)=q2δ(q2,a)=q3δ(q3,a)=q3δ(q0,b)=q2δ(q1,b)=q2δ(q2,b)=q3δ(q3,b)=q1δ(q0,a)=q2δ(q0,b)=q2δ (q1,a)=q2δ(q1,b)=q2δ(q2,a)=q3δ(q2,b)=q3δ(q3,a)=q3δ(q3,b)=q1 Find a minimal equivalent dfa.

9. Minimize the number of states in the dfa in Figure 2.16.

THEOREM 2.2 Let L be the language accepted by a nondeterministic finite accepter MN = (QN, Σ, δN, q0, FN). Then there exists a deterministic finite accepter MD = (QD, Σ, δD, {q0}, FD) such that L = L (MD).

10. 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?