An Introduction to Formal Languages and Automata, 7th Edition

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₁ and M₂, are said to be equivalent if

$$L\left(M_1\right)=L\left(M_2\right)\text{},$$

that is, if they both accept the same language.

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