An Introduction to Formal Languages and Automata, 7th Edition

A.5 MEALY MACHINE MINIMIZATION

For a given function Σ^* → Γ^*, there are many equivalent finite-state transducers, some of them differing in the number of internal states. For practical reasons it is often important to find the minimal fst, that is, the machine with the smallest 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₁ and q₂ serve the same purpose ...