State Minimization — Implication Table and Partitioning Method

Why Minimize States?

Fewer states → fewer flip-flops → smaller, cheaper circuit. State minimization finds the smallest equivalent FSM.

Two states are equivalent if:

1. They produce the same output for all inputs, AND
2. For every input, their next states are also equivalent

Implication Table Method

1. Draw a table with state pairs (all combinations)
2. Mark pairs with different outputs as NOT equivalent (X)
3. For remaining pairs, list implied pairs (next-state pairs)
4. Iteratively mark pairs whose implications are marked X
5. Remaining unmarked pairs are equivalent

Example: Minimize the following FSM (Moore, single output):

Step 1: Mark pairs with different outputs:

• A,B(0,0)✓ — A,C(0,1)✗ — A,D(0,1)✗ — A,E(0,0)✓ — A,F(0,1)✗
• B,C(0,1)✗ — B,D(0,1)✗ — B,E(0,0)✓ — B,F(0,1)✗
• C,D(1,1)✓ — C,E(1,0)✗ — C,F(1,1)✓
• D,E(1,0)✗ — D,F(1,1)✓
• E,F(0,1)✗

Step 2: For unmarked pairs, check implied pairs:

• A,B: implied (B,A) and (C,D) — need to check C,D
• A,E: implied (B,A) and (C,E) — C,E is ✗ → mark A,E ✗
• B,E: implied (A,A) and (D,E) — D,E is ✗ → mark B,E ✗
• C,D: implied (E,E) and (F,F) — both same state = equivalent ✓
• C,F: implied (E,A) and (F,F) — E,A check → marked ✗ → mark C,F ✗
• D,F: implied (E,A) and (F,F) — E,A ✗ → mark D,F ✗

Step 3: Remaining equivalent pairs: A≡B, C≡D

Reduced states: {A,B}→P, {C,D}→Q, E, F

Reduced from 6 states to 4 states (saves 1 flip-flop).

Interview Questions

Q1: When can two states never be equivalent? Two states producing different outputs can never be equivalent, regardless of their transitions. Output equivalence is the first necessary condition.

Q2: What is the complexity of state minimization? The implication table method has O(n²) pairs to check, with O(n²) iterations in the worst case, giving O(n⁴) overall. For large FSMs, more efficient algorithms (Hopcroft's algorithm: O(n log n)) are used.

Q3: Does state minimization change the FSM's behavior? No. A minimized FSM and its original are equivalent — they produce identical outputs for every possible input sequence. Minimization only reduces hardware complexity, not functionality.