Section 2.3
2. Just follow the procedure nfa-to-dfa. This gives the dfa
7. Introduce a new final state p f and for every q ∈ F add the transitions
Then make p f the only final state. It is a simple matter then to argue that if
δ * (q 0 , w) ∈ F originally, then δ * (q 0 , w) = {p f } after the modification, so
both the original and the modified nfa's are equivalent.
Since this construction requires λ-transitions, it cannot be made for dfa's.
Generally, it is impossible to have only one final state in a dfa, as can be
seen by constructing a dfa that accepts {λ, a}.
8. Getting an answer requires some thought. One solution is
11. Suppose that L = {w 1 , w 2 ,…w m }. Then the nfa
2. Just follow the procedure nfa-to-dfa. This gives the dfa
7. Introduce a new final state p f and for every q ∈ F add the transitions
Then make p f the only final state. It is a simple matter then to argue that if
δ * (q 0 , w) ∈ F originally, then δ * (q 0 , w) = {p f } after the modification, so
both the original and the modified nfa's are equivalent.
Since this construction requires λ-transitions, it cannot be made for dfa's.
Generally, it is impossible to have only one final state in a dfa, as can be
seen by constructing a dfa that accepts {λ, a}.
8. Getting an answer requires some thought. One solution is
11. Suppose that L = {w 1 , w 2 ,…w m }. Then the nfa