State minimization techniques: Exercises — Hardware deep dive

Prerequisites used here: Finite State Machines, Mealy vs Moore Machines, Flip-Flops, State Assignment (Encoding), Karnaugh Maps, Myhill–Nerode Theorem. Prefer Hindi? See 3.4.12 State minimization techniques (Hinglish).

$P_{0}$ splits only on the current output, because a length-0 string reveals nothing about the future — all it can "measure" is what the state emits right now. Outputs: A = 0, B = 0, C = 1. So C is immediately distinguishable from A and B. $P_{0} = {A, B} {C}$ . A and B share output 0, so they are not yet separated — they might still split later, or might merge. At $P_{0}$ we only know C is different.

Problem 1.2

True or false: "If two states have the same output row, they are equivalent." Justify in one line.

Recall Solution 1.2

False. Same output is only the first condition ( $P_{0}$ ). Equivalence also requires that for every input the next states are themselves equivalent (the "Same-Next" condition). Same output now, different futures ⇒ not equivalent.

Level 2 — Application

Problem 2.1

Minimise this Moore machine by successive refinement. Show $P_{0}, P_{1}, \dots$ until stable, then give the merged state count.

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

Recall Solution 2.1

P0 (by output): outputs A,B = 0; C,D = 1. $P_{0} = {A, B} {C, D}$ Call block $1 = {A, B}$ , block $2 = {C, D}$ .

P1 (check where each state jumps, and which block that landing sits in):

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

A,B share signature $(1, 2)$ ; C,D share $(2, 1)$ . No block split! $P_{1} = {A, B} {C, D} = P_{0}$

Stable already. Partition unchanged ⇒ terminate. $P_{\infty} = {A, B} {C, D}$ Merge ${A, B} \to S$ , ${C, D} \to T$ . 4 states → 2 states. With 2 states we now need only $⌈ lo g_{2} 2 ⌉ = 1$ flip-flop instead of $⌈ lo g_{2} 4 ⌉ = 2$ — a flip-flop saved.

Problem 2.2

Take the minimised result of 2.1 and write the reduced state table ( $S = {A, B}$ , $T = {C, D}$ ).

Recall Solution 2.2

Pick any representative from each block; every member of a block behaves the same. From $A$ : on 0 → $B \in S$ , on 1 → $C \in T$ , output 0. From $C$ : on 0 → $D \in T$ , on 1 → $B \in S$ , output 1.

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

Level 3 — Analysis

Problem 3.1

A refinement that takes two passes to stabilise (a chain reaction). Minimise:

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

Recall Solution 3.1

P0 (by output): D = 1; everyone else = 0. $P_{0} = {A, B, C, E} {D}$ block $1 = {A, B, C, E}$ , block $2 = {D}$ .

P1:

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

C leaks into block 2 on input 0 (it reaches D, the special state) — everyone else stays in block 1. $P_{1} = {A, B, E} {C} {D}$ Now three blocks: $α = {A, B, E}$ , $β = {C}$ , $γ = {D}$ .

P2 (chain reaction — re-check with the new blocks):

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

B now differs: on input 0 it reaches $C$ , which sits in the fresh block $β$ . B splits off. $P_{2} = {A, E} {B} {C} {D}$ Blocks: ${A, E}, {B}, {C}, {D}$ .

P3 (verify stability): only ${A, E}$ has more than one member.

State	on 0 → block	on 1 → block	signature
A	B → {B}	E → {A,E}	({B},{A,E})
E	E → {A,E}	A → {A,E}	({A,E},{A,E})

Different signatures ⇒ A and E split too! $P_{3} = {A} {B} {C} {D} {E}$ All singletons. Machine is already minimal — nothing merges. The interesting lesson is that it took three passes of splitting to prove it; had we stopped after $P_{1}$ we'd have wrongly merged A, B, E.

Problem 3.2

In the machine of 3.1, using the shortest input string, distinguish states B and E (prove they are not equivalent by exhibiting the outputs).

Recall Solution 3.2

They split in $P_{2}$ , so a length-2 string should separate them. Read outputs as we walk (Moore output = output of the state we are currently in; here we list the output of each landing state).

Try input string "0 0":
- From B: $B 0 C 0 D$ . Landing-state outputs: $C$ gives 0, $D$ gives 1. Output sequence = (0, 1).
- From E: $E 0 E 0 E$ . Outputs: $E$ gives 0, $E$ gives 0. Output sequence = (0, 0).
The second output differs (1 vs 0), so "0 0" distinguishes B and E. ✓

Level 4 — Synthesis

Problem 4.1

A Mealy machine. Output now depends on state and input, so each state has an output row (one output per input). Minimise it, then state how many flip-flops the reduced machine needs.

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

Recall Solution 4.1

P0 for Mealy = group by the entire output ROW $(o u t (0), o u t (1))$ , not a single value.

A: (0,0), B: (0,0), C: (0,1), D: (0,1). $P_{0} = {A, B} {C, D}$ block $1 = {A, B}$ , block $2 = {C, D}$ .

P1 (next-state blocks per input):

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

A,B share $(2, 1)$ ; C,D share $(2, 2)$ . No split. $P_{1} = {A, B} {C, D} = P_{0} \Rightarrow stable.$ Merge ${A, B} \to S$ , ${C, D} \to T$ . 4 → 2 states.

Reduced Mealy table (representative $A$ for $S$ , $C$ for $T$ ):

State	N(0)	N(1)	out(0)	out(1)
S	T	S	0	0
T	T	T	0	1

Flip-flops: $⌈ lo g_{2} 2 ⌉ = 1$ . One flip-flop suffices (down from 2).

Problem 4.2

For the reduced machine of 4.1, do a 1-bit state assignment ( $S = 0$ , $T = 1$ ) and write the next-state and output equations. (This ties into State Assignment (Encoding) and Karnaugh Maps.) Let $Q$ be the current state bit, $x$ the input.

Recall Solution 4.2

Encode $S \to Q = 0$ , $T \to Q = 1$ . Next-state bit $Q^{+}$ = 1 iff we land in $T$ .

$Q$	$x$	next state	$Q^{+}$	output
0 (S)	0	T	1	0
0 (S)	1	S	0	0
1 (T)	0	T	1	0
1 (T)	1	T	1	1

Read $Q^{+}$ from the table: it is 1 in every row except $Q = 0, x = 1$ . That single 0 pattern is $\overline{Q} x$ , so $Q^{+} = \overline{\overline{Q} x} = Q + \overline{x} .$ Output is 1 only in row $Q = 1, x = 1$ : $out = Q x .$ One flip-flop holding $Q$ , one OR gate, one AND gate — the entire minimised machine.

Level 5 — Mastery (edge cases & proof)

Problem 5.1 (degenerate: unreachable state)

Minimise, and note anything unusual:

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

Recall Solution 5.1

First check reachability (minimisation of behaviour only counts reachable states). Start at A. From A we reach A, B. From B we reach A, B. C is never reached from the start — no input string leads into it. C is a phantom: it can be deleted outright before we even run refinement.

After deleting C: states ${A, B}$ .
P0 (by output): A = 0, B = 0 → ${A, B}$ together.
P1: A: on 0 → A (block 1), on 1 → B (block 1) → $(1, 1)$ . B: on 0 → A (1), on 1 → B (1) → $(1, 1)$ . Same signature. $P_{\infty} = {A, B} \Rightarrow merge to one state.$ Final machine: a single state with self-loops, output 0. Lesson: strip unreachable states before minimising — otherwise you might "merge" C with nothing and keep a state that can never fire, wasting a flip-flop.

Problem 5.2 (worst-case depth)

The refinement bound says convergence takes at most $N - 1$ passes. Construct a 4-state Moore machine where the very last state to separate does so only at $P_{3}$ (i.e. needs $N - 1 = 3$ refinement passes), and confirm the chain.

Recall Solution 5.2

Reuse the reachable core of Problem 3.1's spirit — a chain $A \to B \to C \to D$ where only $D$ outputs 1:

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

P0: ${A, B, C} {D}$ (D lone output 1). blocks $1 = {A, B, C}$ , $2 = {D}$ .
P1: A: (B→1, A→1)=(1,1). B: (C→1, A→1)=(1,1). C: (D→2, A→1)=(2,1). C splits out. $P_{1} = {A, B} {C} {D}$ .
P2: blocks $α = {A, B}$ , $β = {C}$ , $γ = {D}$ . A: (B→α, A→α)=(α,α). B: (C→β, A→α)=(β,α). B splits out. $P_{2} = {A} {B} {C} {D}$ .
P3: all singletons — a verification pass confirms no change.

The last split (A vs B) happened at $P_{2}$ , and it took a full $N - 1 = 3$ passes (including the final confirming pass) to reach stability. The machine is already minimal, but this shows the $N - 1$ bound is tight: distinguishing information propagates one link back along the chain per pass.

Problem 5.3 (all-equivalent extreme)

What does minimisation yield for a machine where every state has the same output and every state, on every input, goes to a state with that same output? Give the reduced machine.

Recall Solution 5.3

P0: all states share the single output → one block ${$ all states $}$ .
P1: every state, on every input, lands inside that one block → every signature is identical → no split.
Partition never refines: $P_{\infty} = {$ all states $}$ .
Reduced machine = a single state with self-loops on every input, emitting the constant output. This is the extreme opposite of Problem 3.1: maximal merging. By Myhill–Nerode Theorem this single-state machine is the unique minimal one, since the language it recognises makes no distinctions at all.

Wrap-up recall

Recall Quick self-check

When is $P_{0}$ built from output rows not single outputs? ::: For Mealy machines, because a Mealy state's output depends on the input, so its identity is the whole row. Why compare landing blocks not landing state names? ::: Equivalence merges states, so two different landing states in the same block count as "the same future"; names alone would over-split. What must you do to unreachable states before minimising? ::: Delete them first — their behaviour is irrelevant and they would inflate the final state count and flip-flop cost. Refinement terminates when? ::: When a full pass produces no change, $P_{k + 1} = P_{k}$ ; at most $N - 1$ passes.

Exercises — State minimization techniques

Level 1 — Recognition

Problem 1.1