As mentioned, there are generally many accepters for a given language, so
any dfa or nfa has many equivalent accepters.
Example 2.11
The dfa shown in Figure 2.11 is equivalent to the nfa in Figure 2.9 since they
both accept the language {(10) n : n ≥0}.
Figure 2.11
When we compare different classes of automata, the question invariably
arises whether one class is more powerful than the other. By “more powerful”
we mean that an automaton of one kind can achieve something that cannot be
done by any automaton of the other kind. Let us look at this question for finite
accepters. Since a dfa is in essence a restricted kind of nfa, it is clear that any
language that is accepted by a dfa is also accepted by some nfa. But the converse
is not so obvious. We have added nondeterminism, so it is at least conceivable
that there is a language accepted by some nfa for which, in principle, we cannot
find a dfa. But it turns out that this is not so. The classes of dfa's and nfa's are
equally powerful: For every language accepted by some nfa there is a dfa that
accepts the same language.
This result is not obvious and certainly has to be demonstrated. The
argument, like most arguments in this book, will be constructive. This means
that we can actually give a way of converting any nfa into an equivalent dfa. The
construction is not hard to understand; once the idea is clear it becomes the
starting point for a rigorous argument. The rationale for the construction is the
following. After an nfa has read a string w, we may not know exactly what state
it will be in, but we can say that it must be in one state of a set of possible states,
say {q i ,q j ,…,q k }. An equivalent dfa after reading the same string must be in
some definite state. How can we make these two situations correspond? The
answer is a nice trick: Label the states of the dfa with a set of states in such a
any dfa or nfa has many equivalent accepters.
Example 2.11
The dfa shown in Figure 2.11 is equivalent to the nfa in Figure 2.9 since they
both accept the language {(10) n : n ≥0}.
Figure 2.11
When we compare different classes of automata, the question invariably
arises whether one class is more powerful than the other. By “more powerful”
we mean that an automaton of one kind can achieve something that cannot be
done by any automaton of the other kind. Let us look at this question for finite
accepters. Since a dfa is in essence a restricted kind of nfa, it is clear that any
language that is accepted by a dfa is also accepted by some nfa. But the converse
is not so obvious. We have added nondeterminism, so it is at least conceivable
that there is a language accepted by some nfa for which, in principle, we cannot
find a dfa. But it turns out that this is not so. The classes of dfa's and nfa's are
equally powerful: For every language accepted by some nfa there is a dfa that
accepts the same language.
This result is not obvious and certainly has to be demonstrated. The
argument, like most arguments in this book, will be constructive. This means
that we can actually give a way of converting any nfa into an equivalent dfa. The
construction is not hard to understand; once the idea is clear it becomes the
starting point for a rigorous argument. The rationale for the construction is the
following. After an nfa has read a string w, we may not know exactly what state
it will be in, but we can say that it must be in one state of a set of possible states,
say {q i ,q j ,…,q k }. An equivalent dfa after reading the same string must be in
some definite state. How can we make these two situations correspond? The
answer is a nice trick: Label the states of the dfa with a set of states in such a