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

Dfa minimization

In computer science, more specifically in the branch of automata theory, DFA minimization is the task of transforming a given deterministic finite automaton into an equivalent DFA that has minimum number of states. Here, two DFAs are called equivalent if they describe the same regular language...

.

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 can be 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 output

Output

Output is the term denoting either an exit or changes which exit a system and which activate/modify a process. It is an abstract concept, used in the modeling, system design and system exploitation.-In control theory:...

s 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 .

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.