State Reduction

State reduction is the optimization of a Sequential circuit by removing redundant states. Fewer states means fewer flip-flops needed to encode the state, which means smaller, cheaper, faster circuits.

States are redundant if they are equivalent to another state: they produce the same output for every input and transition to the same next state (or a pair of equivalent states). Equivalent states can be merged without changing the FSM’s input-output behavior.

Why redundancy happens

When you design an FSM from a verbal specification or via a state-table-by-cases approach, it’s easy to introduce redundant states:

• Two states that “feel” different but actually behave identically.
• Multiple paths through the design that converge at functionally equivalent points.
• Symmetric situations encoded with separate states.

Reducing them shrinks the state register: $n$ states need $\lceil {\log }_{2}n\rceil$ flip-flops. Going from 9 states to 5 saves a flip-flop.

Equivalence definition

Two states $p$ and $q$ are equivalent if, for every input sequence applied starting from $p$ versus from $q$, the FSM produces the same output sequence. Equivalently (and more usefully for the algorithm): $p\equiv q$ iff for every input $x$,

1. The output produced by the pair $(p,x)$ equals the output produced by $(q,x)$, and
2. The next state from $p$ on $x$ is equivalent to the next state from $q$ on $x$.

The two FSM styles attach the output to different things:

• Moore machine. Output depends only on the current state. Condition (1) reduces to ”$p$ and $q$ have the same state output.” If the outputs disagree, $p\not\equiv q$ regardless of inputs.
• Mealy machine. Output depends on the (state, input) pair. Condition (1) must hold for each input: if $p$ and $q$ produce different outputs on even a single input, they are not equivalent. This is a strictly stronger requirement than the Moore version.

Always check the right condition for the machine style. Applying the Moore-style “same state output” check to a Mealy FSM will incorrectly merge states whose transition outputs differ.

Implication table method

The standard algorithm: build an implication table, a triangular table with one cell per unordered pair of distinct states. Fill each cell with either “definitely non-equivalent” (×) or a list of next-state pairs the equivalence depends on.

Algorithm

1. Initial cull. For each pair $(p,q)$:
   • Moore: mark × if $p$ and $q$ have different state outputs.
   • Mealy: mark × if there exists any input $x$ for which $p$ and $q$ produce different transition outputs.
2. List dependencies. For each surviving pair, write the next-state pair $(p^{\prime },q^{\prime })=(\delta (p,x),\delta (q,x))$ for every input $x$. The equivalence of $(p,q)$ implies the equivalence of every listed pair.
3. Propagate. If any listed dependency is marked ×, mark the current pair × too. Repeat until no change.
4. Read off equivalences. Cells that survive are equivalent pairs. Combine them into equivalence classes (transitively: if $p\equiv q$ and $q\equiv r$ then $p\equiv r$).

Worked example (Moore machine)

State table (input alphabet $\{0,1\}$, single-bit state output):

state	next on 0	next on 1	output
a	b	c	0
b	a	d	0
c	a	d	0
d	b	c	1

Step 1, initial cull by output. State $d$ has output 1; all others have output 0. Mark every pair containing $d$ as ×: $a$–$d$, $b$–$d$, $c$–$d$ all eliminated.

Surviving pairs: $a$–$b$, $a$–$c$, $b$–$c$.

Step 2, list dependencies for each:

• $a$–$b$ on input 0: $(b,a)$ → same as $a$–$b$, trivial. On input 1: $(c,d)$ → already ×. So $a$–$b$ depends on a × pair → mark ×.
• $a$–$c$ on input 0: $(b,a)$ → same as $a$–$b$. On input 1: $(c,d)$ → already ×. Mark ×.
• $b$–$c$ on input 0: $(a,a)$ → trivial (same state). On input 1: $(d,d)$ → trivial. No × dependencies → equivalent.

Step 3, propagate. After marking $a$–$b$ and $a$–$c$, no other pairs depend on them, so we’re stable.

Result: $b\equiv c$, all other distinct pairs non-equivalent. Merge $c$ into $b$, replace every “next state $c$” with “next state $b$“:

state	next on 0	next on 1	output
a	b	b	0
b	a	d	0
d	b	b	1

3 states instead of 4 — saves a flip-flop ($\lceil {\log }_{2}3\rceil =2$, same as for 4, so this particular machine doesn’t shrink the register, but the logic gets simpler and a 4→3 reduction does help when starting from, say, 5→4 or 9→8).

The Mealy-machine procedure is identical in shape; only Step 1 changes (compare per-input transition outputs instead of per-state outputs).

After reduction

Once you’ve identified equivalent states, merge them in the state table:

• Pick one representative per equivalence class.
• Replace every reference to a redundant state with its representative.
• Remove the redundant state’s row from the table.

The reduced state table can then be encoded with fewer flip-flops. See State Assignment for the next step.

Limits

State reduction is a polynomial-time algorithm. For very large FSMs, more sophisticated minimization algorithms exist. Hopcroft’s algorithm runs in $O(ns\log n)$ for DFA minimization, where $n$ is the number of states and $s$ is the alphabet size. Texts often quote "$O(n\log n)$" by treating $s$ as a constant; for typical hardware FSMs with a fixed input alphabet that’s fine, but the alphabet factor matters when $s$ grows.

Reduction is helpful but not always dramatic. A well-designed state table from the start has few or no redundant states. Reduction is most useful when the FSM was generated automatically or by composition of multiple sub-machines.