DFA NFA - Theory of Computation

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

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

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

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

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