number of internal states.
The first step in minimizing a Mealy machine is to remove the states that
play no role in any computation because they cannot be reached from the initial
state. When there are no inaccessible states, the fst is said to be connected. But a
Mealy machine can be connected and yet not be minimal, as the next example
illustrates.
Example A.7
The Mealy machine in Fig A.7(a) is connected, but it is clear that the states q 1
and q 2 serve the same purpose and can be combined to give the machine in
Figure A.7(b).
Figure A.7
Definition A.5
Let M = (Q, ∑, Γ, δ, θ, q 0 ) be a Mealy machine. We say that the states q i and q j
are equivalent if and only if
θ* (q i , w) = θ* (q j , w)
for all w ∈ ∑*. States that are not equivalent are said to be distinguishable.