An Introduction to Formal Languages and Automata, 7th Edition

A.6 MOORE MACHINE MINIMIZATION

The minimization of a Moore machine follows the pattern of the minimization of Mealy machines, but there are some differences. While Definition A.5 and A.6 apply to Moore machines, Theorem A.4 needs to be modified.

THEOREM A.6

1. Two states q_i and q_j of a Moore machine are 0-distinguishable if

   $$\theta (q_i)\ne \theta (q_j).$$

2. The two states are k-distinguishable if they are (k − 1)-distinguishable or if there exists an a ∈ Σ such that δ(q_i, a) = q_r and δ(q_j, a) = q_s, where q_r and q_s are (k − 1)-distinguishable.

Proof: The argument here is essentially the same as in Theorem A.4. ■

For the Moore machine minimization we first use the Mealy machine partition procedure to partition the states into equivalence classes and use them following ...