Moore reduction procedure

In computer science, the Moore reduction procedure is a method used for DFA minimization.

The concept is to start assuming that every state may be able to combine with every other state, then separate distinguishable states into separate groups called equivalence partitions. When no more equivalence partitions contain distinguishable states, the states remaining in the same group as other states are combined. Equivalence partitions are numbered by the number of steps it took to get to that point. The 0th partition contains all the states in one group, the 1st partition contains states grouped by their outputs only. Every partition from then on has groupings that are based on which group from the previous partition those states' next state fell under. The procedure is complete when partition n is the same as partition $n+1$.

States that are distinguishable on the k^th partition are called k-distinguishable states. States that are in the same group on the k^th partition are called k-equivalent. Note that states that are k-equivalent at one point are not necessarily equivalent states, as they may be separated into separate groups in a higher partition.

The procedure is as follows:

1. separate states into groups that have the same immediate output for the same current input,
2. distinguish states whose next state(s) are in different groups,
3. regroup the states and repeat the above step until no more states are distinguishable.

See also

• Implication table

References

• Ralf Lämmel; Joost Visser; João Saraiva (8 October 2008). Generative and Transformational Techniques in Software Engineering II: International Summer School, GTTSE 2007, Braga, Portugal, July 2-7. 2007, Revised Papers. Springer. pp. 483–. ISBN 978-3-540-88643-3.