complete.
Minimum Mealy Machine Construction Let M = (Q, ∑, Γ, δ, θ, q 0 ) be the
Mealy machine for which we want to construct a minimal equivalent machine P
= (Q P , ∑, Γ, δ P , θ P , Q P ), where Q P = {E 1 , E 2 ,…, E m }. First we find the
equivalence classes E 1 , E 2 ,…, E m using the partition procedure and create states
labeled E 1 , E 2 ,…, E m for P. Pick an element q i from E r and an element q j from
E s . If δ (q i , a) = q j and θ(q i, a ) = b, define the transition function for P by
δ P (E r , a) = E s
and output by
θ P (E r , a) = b.
If the start state for M is q 0 , the start state for P will be E p so that q 0 is in the
equivalence class Ep. It is a straightforward exercise to show that P is the
minimal equivalent of M. It also follows from Theorem A.5 that a minimal
Mealy machine is unique within a simple relabeling of the states.
Example A.8
Consider the Mealy machine in Figure A.10. Step 1 produces the equivalence
partitioning {q 0 , q 4 }, {q 1 , q 2 }, {q 3 }. In the second step we find that δ(q 0 , a) = q 1 ,
δ(q 4 , a) = q 3 . Since q 1 and q 3 are distinguishable, so are q 0 and q 4 and the new
partition is
E 1 = {q 0 }, E 2 = {q 1 , q 2 }, E 3 = {q 3 }, E 4 = {q 4 }.
Another pass though step 2 yields no further refinement and the partitioning if
finished. From it, we construct the minimal Mealy machine in Figure A.11.
Figure A.10