State minimization techniques: Worked examples — Hardware deep dive

Definition Block labels,

$P_{k}$ , and $P_{\infty}$ — read this before the examples

Block labels ( $1, 2, α, β, \dots$ ). Each refinement pass produces a partition — a set of blocks. We give each block a name so we can write signatures compactly. The rule for assigning them is simple and fixed: list the blocks in the order they appear reading the state table top to bottom, and number them $1, 2, 3, \dots$ (or letter them $α, β, γ$ ). The name itself carries no meaning — it is just a tag so " $N (0)$ lands in block 1" is unambiguous. Two states get the same signature iff their next-states land in the same-named blocks.
$P_{k}$ is the partition after the $k$ -th refinement pass. $P_{0}$ groups by output; each further pass splits blocks whose members have different signatures.
$P_{\infty}$ (read "P-infinity") is the partition you reach once refinement stops changing — i.e. the first $k$ with $P_{k + 1} = P_{k}$ . Because there are finitely many states, this always happens in at most $N - 1$ passes. $P_{\infty}$ is the set of equivalence classes: its blocks are the states of the minimal machine. Whenever you see $P_{\infty}$ below, it means "the final, stable partition".

Figure s01 draws that fingerprint idea concretely — a single state P whose $N (0)$ lands in block 1 and whose $N (1)$ lands in block 2, giving signature $(1, 2)$ . Keep it in mind: every example below is literally "read $N (0)$ and $N (1)$ , write down the block each lands in, compare fingerprints".

We use exactly this picture in Example 1: there state B's $N (0) = A$ (block 1) and $N (1) = D$ (block 2), so B's fingerprint is the $(1, 2)$ shown in s01 — that is the "P" of the figure.

The scenario matrix

Every state-minimization problem you will ever see is one (or a blend) of the cells below. The last column tells you which worked example covers it.

#	Case class	What makes it tricky	Covered by
C1	Moore, nothing merges	already minimal; must prove it	Example 1
C2	Moore, one pair merges	single split, then stable	Example 2
C3	Chain-reaction split	a $P_{2}$ split re-triggers a $P_{3}$ split	Example 3
C4	Everything collapses	all states equivalent → 1 state	Example 4
C5	Mealy machine	$P_{0}$ groups by output row, not single output	Example 5
C6	Degenerate: unreachable state	a state no input can reach — drop it first	Example 6
C7	Implication-chart method	same answer, different tool; sweep to stable	Example 7
C8	Real-world word problem	a serial pattern detector; translate then minimize	Example 8
C9	Exam twist: self-loop trap	a state that loops to itself looks unique but isn't	Example 9

Recall Why enumerate cases at all?

Because the algorithm never changes but the traps do. Each cell above is a place students lose marks: forgetting Mealy uses output-rows (C5), stopping after one pass (C3), keeping a dead state (C6). Seeing all nine inoculates you.

Example 1 — Moore, nothing merges (cell C1)

Forecast: guess now — do any two of A, B, C, D merge? (Three of them share output 0; feels suspicious.)

$P_{0}$ — split by output. A, B, C emit 0; D emits 1. $P_{0} = {A, B, C} {D}$ Why this step? Length-0 information is just "what do you output right now", i.e. any length-1 distinguisher. D is the lone 1, so it is already told apart from the rest.
$P_{1}$ — compute signatures against $P_{0}$ blocks. Reading top to bottom, block $1 = {A, B, C}$ (appears first), block $2 = {D}$ .

State $N (0)$ → block $N (1)$ → block signature

A B → 1 C → 1 (1,1)

B A → 1 D → 2 (1,2)

C D → 2 A → 1 (2,1)

D D → 2 A → 1 (2,1)

Why this step? Two states can share an output yet "leak" into different blocks under one input — that is exactly a length-2 distinguisher (same output now, different block next). Among the three output-0 states A,B,C all fingerprints differ, so each splits into its own block. (Note B's row is exactly the $(1, 2)$ picture of figure s01: $N (0) = A$ in block 1, $N (1) = D$ in block 2. And D keeps its own block since it never shared a block with A,B,C to begin with.) $P_{1} = {A} {B} {C} {D}$
$P_{2}$ — nothing left to split. Every block is a singleton, so $P_{2} = P_{1}$ . Since the partition stopped changing, $P_{\infty} = P_{1}$ . Why this step? $P_{\infty}$ is defined as the first partition that a further pass leaves unchanged; singletons can never split, so we have reached it.

State	$N (0)$ → block	$N (1)$ → block	signature
A	B → 1	C → 1	(1,1)
B	A → 1	D → 2	(1,2)
C	D → 2	A → 1	(2,1)
D	D → 2	A → 1	(2,1)

Verify: the machine has $4$ states, needs $⌈ lo g_{2} 4 ⌉ = 2$ flip-flops, and stays $4$ . Sanity check by hand: from A the string "1" gives next-state C (out 0), from B the string "1" gives D (out 1) — different, so "1" is a length-1 distinguisher and A ≢ B. Confirmed: no merges, already minimal.

Example 2 — Moore, one pair merges (cell C2)

Forecast: A and C look nearly identical (both go to B on 0). Bet on whether they merge.

$P_{0}$ : outputs — A,B,C = 0; D = 1. $P_{0} = {A, B, C} {D}$ Why? D is the only output-1 state — a length-1 distinguisher splits it off.
$P_{1}$ with block $1 = {A, B, C}$ (first in the table), block $2 = {D}$ :

State $N (0)$ → block $N (1)$ → block signature

A B → 1 C → 1 (1,1)

B B → 1 D → 2 (1,2)

C B → 1 C → 1 (1,1)

A and C share $(1, 1)$ ; B is the odd one out. Why this step? B jumps to output-1 state D on input 1 (block 2), which A and C never do — that is the length-2 distinguisher separating B from A and C. $P_{1} = {A, C} {B} {D}$
$P_{2}$ with, reading top to bottom, $α = {A, C}, β = {B}, γ = {D}$ :

State $N (0)$ $N (1)$ signature

A B (β) C (α) (β,α)

C B (β) C (α) (β,α)

Identical → A and C stay merged. The partition did not change, so $P_{2} = P_{1} = P_{\infty}$ . Why this step? We must re-test the surviving block ${A, C}$ against the new, finer blocks — a split elsewhere could have created a fresh distinguisher (that is what happens in Example 3). Here it does not, so the merge is confirmed stable. $P_{\infty} = {A, C} {B} {D}$

State	$N (0)$ → block	$N (1)$ → block	signature
A	B → 1	C → 1	(1,1)
B	B → 1	D → 2	(1,2)
C	B → 1	C → 1	(1,1)

State	$N (0)$	$N (1)$	signature
A	B (β)	C (α)	(β,α)
C	B (β)	C (α)	(β,α)

Minimized table (rename ${A, C} \to S$ ):

State	N(0)	N(1)	Out
S	B	S	0
B	B	D	0
D	B	D	1

Verify: $4 \to 3$ states. Forecast check — feed "11" from A: A→C (out 0), C→C (out 0) = 00; from C: C→C (out 0), C→C (out 0) = 00. Identical outputs ✓, so A ≡ C was correct.

Example 3 — Chain-reaction split (cell C3)

Forecast: A, B, C all output 0 and all go to E on input 1. Do all three survive together to the end, or does one break off late?

$P_{0}$ : outputs — A,B,C = 0; D,E = 1. $P_{0} = {A, B, C} {D, E}$ Why? Output is the only length-1 distinguisher; it separates the two output values.
$P_{1}$ — reading top to bottom, block $1 = {A, B, C}$ , block $2 = {D, E}$ :

State $N (0)$ → block $N (1)$ → block signature

A B → 1 E → 2 (1,2)

B C → 1 E → 2 (1,2)

C D → 2 E → 2 (2,2)

D D → 2 A → 1 (2,1)

E D → 2 A → 1 (2,1)

C breaks off (its 0-move lands in block 2, not block 1). D and E stay together. Why this step? We check every state's fingerprint against the $P_{0}$ blocks to catch length-2 distinguishers. C's input-0 move reaches an output-1 state, while A's and B's input-0 moves reach output-0 states — that difference splits C from A,B. D and E have identical fingerprints so no length-2 distinguisher separates them yet. $P_{1} = {A, B} {C} {D, E}$
$P_{2}$ — reading top to bottom, $α = {A, B}, γ = {C}, δ = {D, E}$ :

State $N (0)$ $N (1)$ signature

A B (α) E (δ) (α,δ)

B C (γ) E (δ) (γ,δ)

Why this step? After C left in $P_{1}$ , A's 0-move (to B, still in α) and B's 0-move (to C, now in its own block γ) point at different blocks. That is the chain reaction — the earlier split of C created a new length-3 distinguisher between A and B, invisible one pass earlier. $P_{2} = {A} {B} {C} {D, E}$
$P_{3}$ — re-check the surviving block ${D, E}$ under the now-finer blocks. D→(D, A) and E→(D, A) still land in the same blocks, so they stay together. All other blocks are singletons, so the partition is unchanged: $P_{3} = P_{2} = P_{\infty}$ . Why this step? Every earlier split forces one more pass, because a fresh split could have separated D from E. It did not, so ${D, E}$ is a genuine equivalence class and we have reached $P_{\infty}$ . $P_{\infty} = {A} {B} {C} {D, E}$

State	$N (0)$ → block	$N (1)$ → block	signature
A	B → 1	E → 2	(1,2)
B	C → 1	E → 2	(1,2)
C	D → 2	E → 2	(2,2)
D	D → 2	A → 1	(2,1)
E	D → 2	A → 1	(2,1)

State	$N (0)$	$N (1)$	signature
A	B (α)	E (δ)	(α,δ)
B	C (γ)	E (δ)	(γ,δ)

Minimized table (rename ${D, E} \to T$ ):

State	N(0)	N(1)	Out
A	B	T	0
B	C	T	0
C	T	A	0
T	T	A	1

Verify: $5 \to 4$ states. Distinguish A,B by hand: the length-3 string "001" from A gives outputs A→B→C→(0)D = 0,0,1; from B gives B→C→D→(0)D = 0,1,1. They differ at position 2 ✓, so "001" is a length-3 distinguisher and A ≢ B — the late split was real. And D≡E: any string gives identical outputs since their table rows match exactly.

Example 4 — Everything collapses to one state (cell C4)

Forecast: both output 0 forever no matter what. How many states in the minimal machine?

$P_{0}$ : both output 0 → $P_{0} = {A, B}$ . Why? Only one output value exists, so there is no length-1 distinguisher — nothing splits.
$P_{1}$ — one block, reading top to bottom call it $1 = {A, B}$ :

State $N (0)$ → block $N (1)$ → block signature

A B → 1 A → 1 (1,1)

B A → 1 B → 1 (1,1)

Same fingerprint → no split, so $P_{1} = P_{0} = P_{\infty}$ . Why this step? Both next-states stay inside the single block, so no input can send A and B to states that differ — there is no distinguisher of any length. $P_{\infty} = {A, B}$

State	$N (0)$ → block	$N (1)$ → block	signature
A	B → 1	A → 1	(1,1)
B	A → 1	B → 1	(1,1)

Minimized table:

State	N(0)	N(1)	Out
S	S	S	0

Verify: $2 \to 1$ state, needing $⌈ lo g_{2} 1 ⌉ = 0$ flip-flops — a pure combinational circuit that always outputs 0. Any input string from A or B yields all zeros, so A ≡ B ✓.

Example 5 — Mealy machine: group by output row (cell C5)

For a Mealy machine the output sits on the transition, so each state has an output row — one output per input. $P_{0}$ must group by the entire row, not a single value.

Forecast: A and B have identical rows and identical destinations. Merge?

$P_{0}$ — group by output row $(out_{0}, out_{1})$ . A: $(0, 1)$ , B: $(0, 1)$ , C: $(0, 0)$ . $P_{0} = {A, B} {C}$ Why this step? In Mealy, a state's "immediate output" is really two numbers (one per input), so a length-1 distinguisher is any input on which their outputs differ. C's row $(0, 0)$ differs from A,B's $(0, 1)$ on input 1, so input "1" splits C off at once.
$P_{1}$ — reading top to bottom, block $1 = {A, B}$ , block $2 = {C}$ :

State $N (0)$ → block $N (1)$ → block signature

A B → 1 C → 2 (1,2)

B B → 1 C → 2 (1,2)

Identical → merge stays, and the partition did not change, so $P_{1} = P_{0} = P_{\infty}$ . Why this step? We re-test ${A, B}$ against the finer blocks for any length-2 distinguisher; their fingerprints match, so none exists. $P_{\infty} = {A, B} {C}$

State	$N (0)$ → block	$N (1)$ → block	signature
A	B → 1	C → 2	(1,2)
B	B → 1	C → 2	(1,2)

Minimized table ( ${A, B} \to S$ ):

State	N(0)/Out	N(1)/Out
S	S / 0	C / 1
C	S / 0	S / 0

Verify: $3 \to 2$ states. Check A≡B: any input string produces identical output+destination because their rows and next-states are identical entry-for-entry ✓.

Example 6 — Degenerate: an unreachable state (cell C6)

Forecast: before you minimize — is every state actually usable?

Reachability sweep. From the start state A, mark what you can reach: A→{B, A}; B→{A, B}. You land only in ${A, B}$ . Z is never $N (0)$ or $N (1)$ of A or B, so no input string ever reaches Z. Why this step? An unreachable state can never affect behaviour; keeping it inflates the table and can even create phantom "merges". Delete Z before running $P_{0}$ .
Now minimize ${A, B}$ . Both output 0, so $P_{0} = {A, B}$ . Why this step? With Z removed, only the reachable states matter; they share output so no length-1 distinguisher splits them. $P_{1} : A \to (B, A) = (1, 1), B \to (A, B) = (1, 1) \Rightarrow P_{\infty} = {A, B} .$ Why this step? Both fingerprints are $(1, 1)$ , no distinguisher of any length exists, and the partition stabilises — that is $P_{\infty}$ .

Minimized table:

State	N(0)	N(1)	Out
S	S	S	0

Verify: $3$ table-rows → $1$ reachable-and-minimal state. Note that if you had forgotten to drop Z, Z (output 1) would sit in its own $P_{0}$ block and never merge, leaving you claiming "2 states" — wrong, because Z is fiction. Reachable states: ${A, B}$ , minimal size $1$ ✓.

Example 7 — Same machine, implication-chart method (cell C7)

Let us re-solve Example 2 with the pairwise chart-style tool to prove both techniques agree. Recall Example 2's table (A,B,C out 0; D out 1). Figure s02 shows the triangular chart: columns are labelled A, B, C left-to-right; rows are labelled B, C, D bottom-to-top, so a cell at column A / row B is the pair (A,B), and so on. Follow the colours in s02 as we go: white cells are "instantly ✗", amber cells are "✗ after the sweep", and the single cyan cell is the survivor.

Forecast: which single unmarked cell will survive to the end?

Mark different-output pairs ✗ immediately. Any pair containing D (out 1) vs an out-0 state is instantly distinguishable: in the figure these are the entire bottom row (row D) — cells (A,D), (B,D), (C,D), drawn in white and marked ✗. Why this step? Different output now is a length-1 distinguisher — no further checking is needed, the pair can never merge.
Fill remaining cells with implied pairs (the next-state pairs, under each input, that must ALSO turn out equivalent):
- Cell column A / row B = (A,B): on 0 → (B,B) trivially equal; on 1 → (C,D). Implied pair: {C,D}.
- Cell column A / row C = (A,C): on 0 → (B,B); on 1 → (C,C). Both trivial. Implied: none (self-consistent). This is the cyan "KEEP" cell in figure s02.
- Cell column B / row C = (B,C): on 0 → (B,B); on 1 → (D,C). Implied pair: {C,D}. Why this step? Two states merge only if their next-states also merge — the implied pairs are the promises each candidate merge depends on. A cell survives only if all its promises survive.
Sweep. {C,D} is already marked ✗ (from step 1, since C and D have different outputs). So any cell that depends on {C,D} collapses:
- (A,B) needed {C,D} → mark ✗ (the top-left amber cell in s02 flips to X).
- (B,C) needed {C,D} → mark ✗ (the other amber cell flips to X).
- (A,C) had no implication → it stays unmarked (the cyan cell survives). Now repeat the sweep looking for newly-broken promises: nothing else changed, so the chart is stable. Why this step? The sweep propagates "distinguishable" backwards: if a promised pair is broken, the promise-holder is broken too. We iterate until a full pass changes nothing — exactly the same stabilisation criterion as $P_{\infty}$ in the partition method.
Read off survivors. The only unmarked cell is (A,C) — the cyan "KEEP" cell in s02 — so merge A and C. $Equivalent pairs = {A, C} \Rightarrow {A, C} {B} {D}$

Verify: identical to Example 2's $P_{\infty} = {A, C} {B} {D}$ , $4 \to 3$ states. Both methods must agree — Myhill–Nerode guarantees a unique minimal machine ✓.

Example 8 — Real-world word problem (cell C8)

Worked example A serial "even number of 1s" detector, over-built

A junior engineer built a state machine that outputs 1 whenever the number of 1s seen so far is even (counting zero as even). They used 4 states because they tracked parity and whether the last bit was 0 or 1. States:

$E_{0}$ = even parity, last bit 0 · $E_{1}$ = even parity, last bit 1
$O_{0}$ = odd parity, last bit 0 · $O_{1}$ = odd parity, last bit 1 Start = $E_{0}$ . Output = 1 iff parity is even.

State	N(0)	N(1)	Out
$E_{0}$	$E_{0}$	$O_{1}$	1
$E_{1}$	$E_{0}$	$O_{1}$	1
$O_{0}$	$O_{0}$	$E_{1}$	0
$O_{1}$	$O_{0}$	$E_{1}$	0

Forecast: the "last bit" info is decorative — the output only cares about parity. How many states should survive?

$P_{0}$ by output. $E_{0}, E_{1}$ out 1; $O_{0}, O_{1}$ out 0. $P_{0} = {E_{0}, E_{1}} {O_{0}, O_{1}}$ Why this step? Output tracks parity, and output is the only length-1 distinguisher, so the two even states share a block and the two odd states share a block.

$P_{1}$ — reading top to bottom, block $1 = {E_{0}, E_{1}}$ (even), block $2 = {O_{0}, O_{1}}$ (odd):

State	$N (0)$ → block	$N (1)$ → block	signature
$E_{0}$	$E_{0}$ → 1	$O_{1}$ → 2	(1,2)
$E_{1}$	$E_{0}$ → 1	$O_{1}$ → 2	(1,2)
$O_{0}$	$O_{0}$ → 2	$E_{1}$ → 1	(2,1)
$O_{1}$	$O_{0}$ → 2	$E_{1}$ → 1	(2,1)

$E_{0} \equiv E_{1}$ (both $(1, 2)$ ) and $O_{0} \equiv O_{1}$ (both $(2, 1)$ ). No block splits. Why this step? We hunt length-2 distinguishers: within each block the two members have identical fingerprints, so the "last bit" distinction never yields a distinguisher — it is genuinely irrelevant. $P_{1} = {E_{0}, E_{1}} {O_{0}, O_{1}}$

$P_{2}$ — re-check with the same two blocks $EVEN = {E_{0}, E_{1}}$ , $ODD = {O_{0}, O_{1}}$ . Signatures are unchanged from $P_{1}$ , so $P_{2} = P_{1} = P_{\infty}$ . Why this step? The partition already stopped changing at $P_{1}$ ; one confirming pass with no change certifies we have reached $P_{\infty}$ . $P_{\infty} = {E_{0}, E_{1}} {O_{0}, O_{1}}$

Minimized table ( $EVEN = {E_{0}, E_{1}}$ , $ODD = {O_{0}, O_{1}}$ ):

State	N(0)	N(1)	Out
EVEN	EVEN	ODD	1
ODD	ODD	EVEN	0

Verify: $4 \to 2$ states, dropping from $⌈ lo g_{2} 4 ⌉ = 2$ flip-flops to $⌈ lo g_{2} 2 ⌉ = 1$ — a real flip-flop saved! Sanity check the input 1011 from $E_{0}$ vs the minimal machine: $E_{0} 1 O_{1} 0 O_{0} 1 E_{1} 1 O_{1}$ , ending odd (out 0). Minimal: EVEN→ODD→ODD→EVEN→ODD, ending odd (out 0). Match ✓. (1011 has three 1s = odd, correct.)

Example 9 — Exam twist: the self-loop trap (cell C9)

Forecast: A loops to itself on input 0; C also loops to itself on input 0. Students often declare A "unique" because of its self-loop. Is it? Do B and C merge, or A and C, or all three?

$P_{0}$ : all output 0 → $P_{0} = {A, B, C}$ . Why this step? Only one output value exists, so there is no length-1 distinguisher — nothing splits on output.
$P_{1}$ — one block, reading top to bottom $1 = {A, B, C}$ :

State $N (0)$ → block $N (1)$ → block signature

A A → 1 B → 1 (1,1)

B C → 1 B → 1 (1,1)

C C → 1 B → 1 (1,1)

All three signatures equal $(1, 1)$ — nothing splits. Since the partition is unchanged, $P_{1} = P_{0} = P_{\infty}$ . Why this step? Every next-state (A, B or C) lives inside the single block, so all fingerprints are $(1, 1)$ ; a self-loop is just " $N (0)$ lands in my own block", which is no distinguisher at all. $P_{\infty} = {A, B, C}$

Sanity by hand: from A the string 0 → A (out 0), 00 → A (out 0); the self-loop keeps outputting 0. From B, 0→C (out 0), 00→C (out 0). No output ever differs, so all three merge.

State	$N (0)$ → block	$N (1)$ → block	signature
A	A → 1	B → 1	(1,1)
B	C → 1	B → 1	(1,1)
C	C → 1	B → 1	(1,1)

Minimized table ( ${A, B, C} \to S$ ):

State	N(0)	N(1)	Out
S	S	S	0

Verify: $3 \to 1$ state. The self-loop was a red herring — a loop back to yourself is just "next-state in my own block", exactly what equivalence allows. Any input string from A, B, or C outputs all zeros ✓.

Coverage check — did we hit every cell?

Every cell of the matrix has a worked, verified example. If a future problem feels new, decompose it into these cells — it is always a blend.

Active recall

Recall Answers

Why did A,B split late? ::: Splitting off C in $P_{1}$ made A's 0-move (to B) and B's 0-move (to C) land in different blocks, a new length-3 distinguisher. Mealy $P_{0}$ grouping? ::: On the full output row — one output per input — not a single output value. Why reachability first? ::: Unreachable states never affect behaviour; keeping them inflates the table and can never legitimately merge, giving a wrong minimal count. Why did (A,B) get marked? ::: Its implied pair {C,D} was already ✗ (C and D have different outputs), so (A,B) collapses on sweep. What is P-infinity? ::: The first partition that a further refinement pass leaves unchanged; you have reached it when $P_{k + 1} = P_{k}$ , and its blocks are the equivalence classes.

State	N(0) / Out(0)	N(1) / Out(1)
A	B / 0	C / 1
B	B / 0	C / 1
C	A / 0	A / 0