State minimization

Also called: state reduction, minimizing states, reducing states

Removing redundant states from a state machine by finding and merging equivalent states, without changing its input/output behavior.

A first-draft state machine often has more states than it needs. State minimization finds the equivalent states and merges each group into one, leaving a machine that behaves identically from the outside with as few states as possible.

The simple method, row matching:

Write the state table.
Find two rows with the same outputs and the same next states for every input.
Merge them: delete one row and replace every reference to it with the other.
Repeat until no two rows match.

Row matching can miss pairs that are equivalent only because their next states are equivalent to each other. An implication table handles those systematically.

The payoff: fewer states can mean fewer flip-flops (going from 5 states to 4 saves one), simpler next-state logic, and a design that's easier to understand.

Worked example

Example

Minimizing a 4-state machine

Moore table: A(0): 0 → B, 1 → C. B(0): 0 → A, 1 → D. C(0): 0 → A, 1 → D. D(1): 0 → A, 1 → D.

1.
Rows B and C are identical: output 0, next A on 0, D on 1. Merge C into B.
2.
Update A: on 1 it now goes to B. Table: A(0): B, B. B(0): A, D. D(1): A, D.
3.
Compare again: no two rows have the same output and next states.
4.
Minimal machine: 3 states (the diagram).

Common mistakes

Forgetting to redirect arrows that pointed at the removed state.
Stopping after one pass. A merge can create new identical rows.
Merging states with different outputs.

Practice State minimization

Interactive questions with instant feedback and a worked solution for every wrong answer.

Finite State Machines lesson full course

Practice exams

Learn it step by step

State minimization is taught in Finite State Machines.

Finite State Machines →

All terms