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

to (those) states in the original machine. So we consider f1; 2; 3g to see if it is necessary to
split it. But, as we have seen,
m(1;a) = 3;
m(2;a) = 3; and
m(3;a) = 3:
Also,
m(1;b) = 4;
m(2;b) = 4; and
m(3;b) = 4:
Thus, there is no further state splitting to be done, and we are left with the smaller DFA
in Figure 2.19.
FIGURE 2.19 A minimal DFA recognizing (ajb)ab.
The algorithm for minimizing a DFA is built around this notion of splitting states.
Algorithm 2.4 Minimizing a DFA
Input: a DFA, D = (;S;s 0 ;M;F)
Output: a partition of S
Set partition fSF;Fg // start with two sets: the non-nal states and the nal states
// Splitting the states
while splitting occurs do
for Set set in partition do
if set.size() > 1 then
for Symbol a in do
// Determine if moves from this `state' force a split
State s a state chosen from set S
targetSet the set in the partition containing m(s;a)
Set set1 fstates s from set S; such that m(s;a) 2 targetSetg
Set set2 fstates s from set S; such that m(s;a) 2 targetSetg
if set2 6= fg then
// Yes, split the states.
replace set in partition by set1 and set2 and break out of the for-loop to
continue with the next set in the partition
end if
end for
end if
end for
end while