Therefore in M 1 the input strings aw and bw must produce different output. But
in M 2 they clearly print the same thing. This contradiction implies that, at this
level, the two machines must be identical. Since this reasoning can be extended
to any part of the two machines, the theorem follows.
The minimization of a Mealy machine therefore starts with an identification
of equivalent states.
Partition Algorithm
1. With states Q = {q 0 , q 1 , q n } find all states that are 1-equivalent to q 0 and
partition Q into two sets {q 0 , q i ,…q j } and {q k ,…q l }. The first of these sets
will contain all states that are 1-equivalent to q 0 , the second will contain all
states that are 1-distinguishable from it. Next, we repeat this process with
states q 1 , q 2 ,…, q n . Removing duplicate sets, we are left with a partitioning
based on 1-equivalence.
2. For every pair of states q i and q j in the same equivalence class determine if
there are transitions, as in Theorem A.4, so that there are states q r and q s in
different equivalence classes. If so, create new equivalence classes to
separate them. Check all pairs to find their appropriate equivalence classes.
3. Repeat step 2 until no new equivalence classes are created.
At the end of this procedure, the state set Q will have been partitioned into
equivalence classes E 1 , E 2 ,…, E q so that all members of each class are equivalent
in the sense of Definition A.5.
To justify the procedure, several points have to be addressed. The first is that
after the kth pass though step 2 all elements of an existing equivalence class are
(k + 1)-equivalent. This follows by induction, using part (b) of Theorem A.4.
The second point is that the process must terminate. This is clear since each
pass though step 2 creates at least one new equivalence class, and there can be at
most |Q| such classes.
Finally, we must show that a complete equivalence partitioning has been
achieved when the process stops. This can be seen from part (b) of Theorem A.4.
For a pair (q i , q j ) to be k-distinguishable, there must exist (k – 1)-distinguishable
states q r and q s ; if no such states exist, no states that can be distinguished by
longer strings can exist. Therefore, that equivalence partitioning must be
in M 2 they clearly print the same thing. This contradiction implies that, at this
level, the two machines must be identical. Since this reasoning can be extended
to any part of the two machines, the theorem follows.
The minimization of a Mealy machine therefore starts with an identification
of equivalent states.
Partition Algorithm
1. With states Q = {q 0 , q 1 , q n } find all states that are 1-equivalent to q 0 and
partition Q into two sets {q 0 , q i ,…q j } and {q k ,…q l }. The first of these sets
will contain all states that are 1-equivalent to q 0 , the second will contain all
states that are 1-distinguishable from it. Next, we repeat this process with
states q 1 , q 2 ,…, q n . Removing duplicate sets, we are left with a partitioning
based on 1-equivalence.
2. For every pair of states q i and q j in the same equivalence class determine if
there are transitions, as in Theorem A.4, so that there are states q r and q s in
different equivalence classes. If so, create new equivalence classes to
separate them. Check all pairs to find their appropriate equivalence classes.
3. Repeat step 2 until no new equivalence classes are created.
At the end of this procedure, the state set Q will have been partitioned into
equivalence classes E 1 , E 2 ,…, E q so that all members of each class are equivalent
in the sense of Definition A.5.
To justify the procedure, several points have to be addressed. The first is that
after the kth pass though step 2 all elements of an existing equivalence class are
(k + 1)-equivalent. This follows by induction, using part (b) of Theorem A.4.
The second point is that the process must terminate. This is clear since each
pass though step 2 creates at least one new equivalence class, and there can be at
most |Q| such classes.
Finally, we must show that a complete equivalence partitioning has been
achieved when the process stops. This can be seen from part (b) of Theorem A.4.
For a pair (q i , q j ) to be k-distinguishable, there must exist (k – 1)-distinguishable
states q r and q s ; if no such states exist, no states that can be distinguished by
longer strings can exist. Therefore, that equivalence partitioning must be