Theorem A.5
Let M 1 = (Q, ∑, Γ, δ, θ, q 0 ) be a Mealy machine in which all states are
distinguishable. Then M 1 is minimal and unique (within a relabeling of states).
Proof: Suppose that there exists an equivalent machine M 2 with fewer states
than M 1 . If M2 has fewer states than M 1 , by the pigeonhole principle, at least one
of the states of M2 must combine several functions of the states of M 1 .
Specifically, there must be two strings, each of which leads to a different state in
M 1 , but which both lead to the same state in M2. What possible structure can M2
have?
Suppose, for the sake of illustration, that M 1 has the partial structure shown
in Figure A.8 and we try to combine states q 1 and q 2 for M 2 . To preserve the
equivalence, the partial structures of M 2 must be as shown in Figure A.9. But
since q 1 and q 2 are distinguishable in M 1 , there must be some w so that
Figure A.8
Figure A.9
Let M 1 = (Q, ∑, Γ, δ, θ, q 0 ) be a Mealy machine in which all states are
distinguishable. Then M 1 is minimal and unique (within a relabeling of states).
Proof: Suppose that there exists an equivalent machine M 2 with fewer states
than M 1 . If M2 has fewer states than M 1 , by the pigeonhole principle, at least one
of the states of M2 must combine several functions of the states of M 1 .
Specifically, there must be two strings, each of which leads to a different state in
M 1 , but which both lead to the same state in M2. What possible structure can M2
have?
Suppose, for the sake of illustration, that M 1 has the partial structure shown
in Figure A.8 and we try to combine states q 1 and q 2 for M 2 . To preserve the
equivalence, the partial structures of M 2 must be as shown in Figure A.9. But
since q 1 and q 2 are distinguishable in M 1 , there must be some w so that
Figure A.8
Figure A.9