Lexical Analysis - Introduction to Compiler Construction in a Java World - page 48

is a final state in the DFA. In our example, only s 4 is a final state because it contains (the
final) state 11 from the original NFA.
Putting all of this together, a DFA derived from our NFA for (ajb)ab is illustrated in
Figure 2.16.
FIGURE 2.16 A DFA recognizing (ajb)ab.
We can now give the algorithm for constructing a DFA that is equivalent to an NFA.
2.8 Minimal DFA
So, how do we come up with a smaller DFA that recognizes the same language? Given an
input string in our language, there must be a sequence of moves taking us from the start
state to one of the final states. And, given an input string that is not in our language, there
cannot be such a sequence; we must get stuck with no move to take or end up in a non-final
state.
Clearly, we must combine states if we can. Indeed, we would like to combine as many
states together as we can. So the states in our new DFA are partitions of the states in the
original (perhaps larger) DFA.
A good strategy is to start with just one or two partitions of the states, and then split
states when it is necessary to produce the necessary DFA. An obvious first partition has
two sets: the set of final states and the set of non-final states; the latter could be empty,
leaving us with a single partition containing all states.
For example, consider the DFA from Figure 2.16, partitioned in this way. The partition
into two sets of states is illustrated in Figure 2.17.
The two states in this new DFA consist of the start state, f0; 1; 2; 3g and the nal state
f4g. Now we must make sure that, in each of these states, the move on a particular symbol
reflects a move in the old DFA. That is, from a particular partition, each input symbol must
move us to an identical partition.