State minimization techniques

WHY do we minimize?

WHY it matters: number of states $N$ decides the number of flip-flops $\lceil \log_2 N \rceil$ . Cutting states can drop a flip-flop, shrink the next-state/output logic, save power and area.
WHAT we exploit: redundant states — states that are equivalent to some other state.
HOW we find them: partition the states into groups of "so-far-indistinguishable" states, then keep refining until no group can be split. Whatever survives together is equivalent.

We build the equivalence relation layer by layer using the idea of $k$ -distinguishability.

Derivation of the refinement rule. Let $P_k$ be the partition where two states share a block iff they are NOT $k$ -distinguishable (indistinguishable up to length- $k$ inputs).

$P_0$ (base case): length-0 tells us nothing about future, so we split only on the immediate output. Put states in the same block iff they produce the same output (Moore: same state output; Mealy: same output row for every input).
Inductive step ( $P_{k}\to P_{k+1}$ ): $p,q$ stay together in $P_{k+1}$ iff they were together in $P_k$ AND for every input $x$ , $\delta(p,x)$ and $\delta(q,x)$ lie in the same block of $P_k$ . (Because being distinguishable by a length- $(k{+}1)$ string = "different now" OR "go to states distinguishable by length- $k$ ".)
Termination: each refinement either splits a block or leaves the partition unchanged. Blocks can't refine forever (finite states). When $P_{k+1}=P_k$ , we've reached the coarsest stable partition — this is exactly the equivalence classes. It converges in at most $N-1$ steps.

$P_0 \succeq P_1 \succeq \cdots \succeq P_k = P_{k+1} = P_\infty$

Each final block = one state of the minimal machine (this minimal DFA is unique up to renaming — the Myhill–Nerode result).

Two practical techniques

Fast, systematic, good for machines given as a state table.

2. Implication chart (pairwise) method

List every pair of states in a triangular chart. In each cell:

If the two states have different outputs → mark ✗ (distinguishable) immediately.
Otherwise write the implied pairs: the next-state pairs that must ALSO be equivalent.
Then sweep: if any implied pair gets marked ✗, mark this cell ✗ too. Repeat until stable.
Unmarked cells at the end = equivalent pairs → merge them.

Worked Example 1 — Partitioning (Moore machine)

State table (input $x\in\{0,1\}$ ), output is the Moore state output:

State	N( $x{=}0$ )	N( $x{=}1$ )	Output
A	B	C	0
B	A	D	0
C	D	A	0
D	D	A	1

Step P0 — split by output. Outputs: A,B,C = 0 ; D = 1. $P_0 = \{A,B,C\}\ \{D\}$ Why this step? Length-0 info = current output; D is already distinguishable (it's the only 1).

Step P1 — check next states against $P_0$ blocks. Call block1 $=\{A,B,C\}$ , block2 $=\{D\}$ .

State	on 0	block	on 1	block
A	B	1	C	1
B	A	1	D	2
C	D	2	A	1

Why this step? Two states may share output but "leak" to different blocks — that's a length-2 distinguisher. A→(1,1), B→(1,2), C→(2,1): all three signatures differ. $P_1 = \{A\}\ \{B\}\ \{C\}\ \{D\}$

Step P2: partition can't refine further (all singletons). Stop. Conclusion: no states merge — this machine is already minimal.

Worked Example 2 — states DO merge

State	N(0)	N(1)	Output
A	B	C	0
B	B	D	0
C	B	C	0
D	B	D	1

P0 (by output): $\{A,B,C\}\ \{D\}$ . Why? D is the lone output-1 state.

P1: blocks: 1 $=\{A,B,C\}$ , 2 $=\{D\}$ .

State	on 0 → block	on 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 have the same signature (1,1); B differs. $P_1 = \{A,C\}\ \{B\}\ \{D\}$

P2: re-check with new blocks: $\alpha=\{A,C\}$ , $\beta=\{B\}$ , $\gamma=\{D\}$ .

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

Same signature → A and C stay merged. Partition stable. $P_\infty=\{A,C\}\ \{B\}\ \{D\}$

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

Why this step? 4 states → 3 states. We still need 2 flip-flops here, but the logic simplifies and larger machines often drop a flip-flop. Verify by Forecast: before merging, predict the output of "input = 1,1" from A (A→C, out 0; C→C, out 0) vs from C (C→C, out 0; C→C, out 0) — identical, ✓.

Common mistakes (Steel-man + fix)

Active recall

Recall Feynman: explain to a 12-year-old

Imagine lots of toy robots. Two robots are "the same" if no matter what buttons you press, they beep the same beeps and end up acting the same. If you find twins like that, throw one away — you only need one. To find twins: first group robots that beep the same right now. Then check where each robot walks to; if two "same-beep" robots walk into different groups, they aren't real twins — split them. Keep splitting until nothing changes. The groups left are true twins. Fewer robots = a cheaper toy!

When are two states equivalent?

For every input sequence they give identical output sequences; equivalently same current output AND next states equivalent for every input.

What is the base partition P0 in successive refinement?

Group states purely by their output (Moore: state output; Mealy: full output row over all inputs).

State the refinement rule P_k → P_{k+1}.

Keep p,q together iff already together in P_k AND for every input their next states fall in the same block of P_k.

When does partition refinement stop?

When a full pass produces no change, i.e. P_{k+1}=P_k (the coarsest stable partition); ≤ N−1 steps.

What are k-distinguishable states?

States separable by some input string of length ≤ k, giving different outputs.

In an implication chart, what does a cell mark ✗ mean?

The two states are distinguishable (different outputs, or an implied pair became distinguishable).

In an implication chart, what does a final unmarked cell mean?

The two states are equivalent → merge them.

Why does merging states help hardware?

Fewer states → fewer flip-flops (⌈log2 N⌉) and simpler next-state/output logic → less area/power.

Common mistake about "same output"?

Same output alone (P0) is NOT equivalence; must also reach equivalent next states.

Is the minimized machine unique?

Yes, unique up to state renaming (Myhill–Nerode).

Connections

Finite State Machines — the object we minimize.
Mealy vs Moore Machines — changes how $P_0$ is defined.
State Assignment (Encoding) — done after minimization; sets flip-flop bits.
Flip-Flops — state count → count $\lceil\log_2 N\rceil$ .
Myhill–Nerode Theorem — theoretical basis for the unique minimal DFA.
Karnaugh Maps — combinational simplification analog (both remove redundancy).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ek FSM ke andar bahut saare states hote hain, aur kabhi-kabhi do states bilkul ek jaise "behave" karte hain — matlab jo bhi input do, dono same output dete hain aur aage bhi same jagah pahunchte hain. Aise states ko hum equivalent kehte hain. Agar do states equivalent hain to dono ko rakhne ka koi fayda nahi — ek ko hata do. Isi ko state minimization bolte hain, aur iska seedha faayda: kam states matlab kam flip-flops ( $\lceil\log_2 N\rceil$ ) aur simpler logic, yaani chip chhoti, power kam.

Equivalent check karne ka rule yaad rakho: "Same Out, Same Next". Sirf abhi ka output same hona kaafi nahi (yeh galti sab karte hain!) — next state bhi same group mein jaana chahiye. Isliye hum partitioning karte hain: pehle $P_0$ banao output ke hisaab se, phir har state ka next-state kis block mein jaa raha hai woh dekho, aur jinke signature alag hain unhe alag kar do. Yeh process repeat karte raho jab tak partition change hona band na ho jaye — tab jo groups bache, wahi asli equivalent classes hain.

Doosra tareeka hai implication chart — har pair ke liye ek cell, jahan ya to cross laga do (agar output alag) ya "implied pairs" likh do. Phir sweep karke jinke implied pairs cross ho gaye unhe bhi cross kar do. Aakhir mein jo cell khaali (unmarked) reh gaye — wahi merge karne wale pairs hain. Bas dhyaan rakhna: ek hi pass mein mat ruk jaana, chain reaction ho sakta hai. Iterate karo till no change. Yeh minimal machine unique hota hai (bas naam badal sakte hain) — yeh Myhill–Nerode kehta hai.

WHY do we minimize?

HOW: deriving the partition-refinement algorithm from scratch

Two practical techniques

1. Partitioning (successive refinement) — described above

2. Implication chart (pairwise) method

Worked Example 1 — Partitioning (Moore machine)

Worked Example 2 — states DO merge

Common mistakes (Steel-man + fix)

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sequential Circuits

Connections