Scanning—Theory and Practice - Crafting a Compiler - page 99

procedure S plit ( MergedStates )

repeat
changed ←

false
foreach S ∈ MergedStates , c ∈Σ

do

targets ← T arget B lock ( s , c , MergedStates )

s ∈ S

if | targets |> 1

then
changed ← true

foreach t ∈ targets do
newblock ←{ s ∈ S | T arget B lock ( s , c , MergedStates ) = t }

MergedStates ← MergedStates ∪{ newblock }
MergedStates ← MergedStates −{ S }
until not changed
end

function T ( s , c , MergedStates ) returns MergedState

return B ∈ MergedStates | T ( s , c )

arget B lock

∈ B

end

Figure 3.27: An algorithm to split FA states.

a | d

b c

1 3,6

2,5 4,7

Figure 3.28: The minimum state automaton for Figure 3.26.

is executed, we are essentially done. Transitions between
merged states are the same as the transitions between states in the original
DFA. That is, if there was a transition between states s i and s j under character
c , then there is now a transition under c from the merged state containing
s i to the merged state containing s j . The start state is that merged state that
contains the original start state. An accepting state is a merged state that
contains accepting states (recall that accepting and nonaccepting states are
never merged).

Once S plit

Returning to the example, the minimum state automaton we obtain is
shown in Figure 3.28.

A proof of the correctness and optimality of this minimization algorithm
can be found in most texts on automata theory, such as [HU79].