An Introduction to Formal Languages and Automata, 7th Edition

2.4 REDUCTION OF THE NUMBER OF STATES IN FINITE AUTOMATA*

Any dfa defines a unique language, but the converse is not true. For a given language, there are many dfa’s that accept it. There may be a considerable difference in the number of states of such equivalent automata. In terms of the questions we have considered so far, all solutions are equally satisfactory, but if the results are to be applied in a practical setting, there may be reasons for preferring one over another.

EXAMPLE 2.14

The two dfa’s depicted in Figure 2.17(a) and 2.17(b) are equivalent, as a few test strings will quickly reveal. We notice some obviously unnecessary features of Figure 2.17(a). The state q₅ plays absolutely no role in the automaton since it can never be reached ...