Equivalent states

Also called: state equivalence, redundant states, redundant state

Two states of a state machine that no input sequence can tell apart: they give the same outputs and lead to equivalent next states for every input.

Two states are equivalent if, starting from either one, every possible input sequence produces exactly the same outputs. From the outside you couldn't tell which one the machine started in. That means one of them is redundant.

The practical test:

The two states must have the same outputs (same Moore output, or the same Mealy output for every input).
For every input, their next states must be the same, or themselves equivalent.

The quick case: two rows of a state table that are identical (same output, same next state for every input) are equivalent. Merge them into one state, redirect every arrow that pointed at the removed one, and look again: the merge can make other rows identical.

Why bother? Fewer states can mean fewer flip-flops (5 states need 3, 4 need only 2) and simpler logic. Removing equivalent states is called state minimization; an implication table finds all of them systematically.

Two states with different outputs are never equivalent, however similar their arrows look.

Worked example

Example

Finding and merging a pair

The Moore machine in the diagram has states A, B, C (output 0) and D (output 1).

1.
Rows: A: 0 → B, 1 → C. B: 0 → A, 1 → D. C: 0 → A, 1 → D. D: 0 → A, 1 → D.
2.
B and C have the same output (0) and identical next states (A on 0, D on 1). So B ≡ C.
3.
Merge C into B: A's arrow on 1 now points to B, so A goes to B on either input.
4.
Check the rest: A vs B? A on 1 → B, B on 1 → D, and D's output differs from B's, so A and B are not equivalent. No more merges.
5.
Result: 3 states. That needs 2 flip-flops, the same as 4 states, but the logic is simpler.

Common mistakes

Merging two states with the same arrows but different outputs. Outputs must match first.
Stopping after one merge. Redirecting arrows can make new rows identical.
Requiring identical next states in every case. Next states that are themselves equivalent are enough.

Practice Equivalent states

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

Equivalent states is taught in Finite State Machines.

Finite State Machines →

All terms