742
Modeling Arithmetic, Computation, and Languages
agoRitHm MiniMize
Minimize (finite-state machine table M)
//produces a minimized version of M
Local variable:
boolean flag
//flag for loop exit when nonequivalent states found
find 0-equivalent states of M
repeat
while untested equivalence classes remain do
select untested equivalence class
while untested state pairs in current class remain do
select untested state pair in current class
flag = false
while untried input symbols remain and not flag do
select untried input symbol
for both states in current pair, find next state
under current input symbol
if next states not equivalent then
flag = true
end if
end while
if flag then
mark current states for different classes;
end if
end while
form new equivalence classes
end while
until set of new equivalence classes = set of old equivalence classes
end Minimize
example 36
For the machine M of Examples 34 and 35, the reduced machine M′ will have
states
A = 50, 26
B = 556
C = 51, 66
D = 53, 46
The state table for M′ (Table 9.6) is obtained from that for M. Machine M′ (starting
state A) will reproduce M’s output for any input string, but it has four states instead
of seven.