partition procedure to partition the states into equivalence classes and use them
following the minimization process.
Minimal Moore Machine Construction
Let M = (Q, ∑, Γ, δ, θ, q 0 ) be the Moore machine to be minimized. First we
establish the equivalence classes E 1 , E 2 ,…, E m by the partition algorithm and
create states labeled E 1 , E 2 ,…, E m for the minimized machine P. Pick an element
from E r and an element q j from Es. If δ(q i, a ) = q j and θ(q j ) = b, then the
transition function for P is
δ P (E r , a) = E s
and
θ p (E s ) = b.
This will yield the minimal Moore machine.
There is a minor complication with the minimal Moore machine
construction. The minimization process assigns θ(q o ) to the equivalence state
associated with q 0 . In some cases this can lead to non-uniqueness.
Example A.9
Look at the two Moore machines in Figure A.12. Clearly they are equivalent and
also clearly they are minimal. But since the output for the two initial states are
different, they cannot be made identical by just a relabeling. The difficulty
comes from the fact that the output for the initial state is arbitrary unless that
state can be re-entered. But this is a trivial issue that can be ignored.
Figure A.12