20. Use Definition 2.5 to show that for any nfa for all q ∈Q and all w, v ∈ Σ * .
21. An nfa in which (a) there are no λ-transitions, and (b) for all q ∈ Q and all a
∈ Σ, δ (q,a)contains at most one element, is sometimes called an incomplete
dfa. This is reasonable since the conditions make it such that there is never
any choice of moves.
For Σ = {a,b}, convert the incomplete dfa below into a standard dfa.
22. Let L be a regular language on some alphabet Σ, and let Σ 1 ⊂ Σ be a smaller
alphabet. Consider L 1 , the subset of L whose elements are made up only of
symbols from Σ 1 , that is, Show that L 1 is also regular.
2.3
Equivalence
of
Deterministic
and
Nondeterministic Finite Accepters
We now come to a fundamental question. In what sense are dfa's and nfa's
different? Obviously, there is a difference in their definition, but this does not
imply that there is any essential distinction between them. To explore this
question, we introduce the concept of equivalence between automata.
Definition 2.7
Two finite accepters, M 1 and M 2 , are said to be equivalent if that is, if they both
accept the same language
L(M 1 ) = L(M 2 ),