State minimization techniques: Question bank — Hardware deep dive

Before we start, three symbols you'll see, each in plain words:

$p \equiv q$ ::: read "state $p$ is equivalent to state $q$ " — no input string can ever tell them apart by their outputs.
$P_{k}$ ::: the partition after $k$ refinement rounds — a grouping of states where two states share a group if no input string of length $\leq k$ separates them.
$δ (p, x)$ ::: the next-state function — "starting in state $p$ , feed input $x$ , land here."

True or false — justify

The claim is stated; the reveal gives the verdict and the reasoning.

Two states with the same current output are always equivalent.

False. Same output is only the base partition

P_{0}

; they can still branch to distinguishable futures, e.g. one leads to an output-1 state and the other never does.

If two states are equivalent, then for every input they must land in equivalent states.

True. This is condition 2 of equivalence — if some input sent them to a distinguishable pair, an input string would then expose them, contradicting

p \equiv q

Equivalent states must have the same next state for each input (literally the identical state).

False. They need next states that are equivalent, not identical —

δ (p, x) \equiv δ (q, x)

is enough; the targets can be two different but indistinguishable states.

Minimization can only ever reduce, never increase, the number of states.

True. Refinement merges equivalence classes; it never invents new distinctions beyond those already present, so

N_{m i n} \leq N

State equivalence is an equivalence relation (reflexive, symmetric, transitive).

True.

p \equiv p

trivially; if

p \equiv q

then

q \equiv p

; and indistinguishability chains through, so the classes are disjoint and well-defined.

The minimal machine for a given behaviour is unique up to renaming states.

True. This is the Myhill–Nerode Theorem result — the coarsest stable partition is forced by the machine's input/output behaviour, so any two minimal DFAs are isomorphic.

Refinement always terminates in at most

N - 1

passes for

N

states.

True.

P_{0}

has at least 2 blocks (unless all outputs match), each pass adds

\geq 1

block until stable, and you can't have more than

N

blocks — so at most

N - 1

splits.

A pass that changes the partition means we are finished.

False. A change can trigger a fresh split next round (chain reaction); you stop only when a full pass produces

P_{k + 1} = P_{k}

with no change.

For a Moore machine,

P_{0}

is formed by grouping states that share a single output value.

True. A Moore state emits one output tied to the state itself, so length-0 information is exactly that single value.

For a Mealy machine,

P_{0}

groups states with the same single output value.

False. A Mealy state's output depends on the input, so it has an output row (one output per input);

P_{0}

groups states whose entire rows match across all inputs.

Spot the error

Each line describes a flawed procedure; the reveal names the bug and the fix.

"States A and B both output 0, so I merged them immediately."

Error: skipped the next-state check. Merge needs Same-Out and Same-Next — verify

δ (A, x)

and

δ (B, x)

fall in the same block for every

x

first.

"The partition changed on pass 1, so I stopped and read off the classes."

Error: stopped one pass too early. You must run refinement until a pass leaves the partition unchanged, because a new block can split another.

"In the implication chart I only wrote ✗ marks and ignored the empty cells."

Error: the empty (unmarked, consistent) cells are the answer — those are the equivalent pairs to merge. Ignoring them means merging nothing.

"For this Mealy machine I split

P_{0}

by the output when input = 0 only."

Error: you used a partial output row. Mealy

P_{0}

must match outputs for all inputs, so include input = 1 (and any others) too.

"I found A≡B and C≡D separately, so the minimal machine has 2 states."

Error: merging pairs isn't the same as counting classes. If B and C are also equivalent, transitivity collapses {A,B,C,D} into one class — count the final blocks, not the pairs.

"An implied pair in a cell got marked ✗, but the cell itself was already blank so I left it blank."

Error: you must sweep. If any implied pair becomes ✗, this cell becomes ✗ too, and you repeat until the chart is stable.

"Two states go to each other on input 1 (A→B, B→A) and have equal outputs, so they can't be equivalent — the check loops forever."

Error: a self-referential loop is not a contradiction. If nothing else distinguishes them, mutual/cyclic implications that never hit a ✗ mean the pair is equivalent.

Why questions

Why is the number of states, not the number of transitions, what drives flip-flop count?

Because state must be stored in memory;

⌈ lo g_{2} N ⌉

flip-flops hold one of

N

states. Transitions are combinational logic derived from that stored state — see Flip-Flops and State Assignment (Encoding).

Why does

P_{0}

split on output rather than on next-state?

Because a length-0 input string reveals only the immediate output; the machine hasn't "moved" yet, so the only observable so far is the current output.

Why does dropping states not guarantee dropping a flip-flop?

Flip-flop count is

⌈ lo g_{2} N ⌉

, a step function. Going

4 \to 3

states still needs 2 flip-flops; you save a flip-flop only when you cross a power-of-2 boundary (e.g.

5 \to 4

Why is even a same-flip-flop merge still worth doing?

Fewer states shrink the next-state and output logic (fewer minterms), which cuts area, power, and delay — and simplifies the Karnaugh Maps you draw for that logic.

Why must we check all inputs when testing next-state equivalence, not just one?

A single input string of any composition can act as a distinguisher; if even one input sends

p

and

q

into different blocks, they are distinguishable, so partial checks can wrongly merge.

Why does the algorithm converge to the coarsest stable partition and not just any stable one?

Refinement only ever splits (never rejoins), starting from the coarsest split-by-output. So it stops at the first — hence coarsest — partition that no rule can split further, which is exactly the equivalence classes.

Why is Moore-to-Mealy conversion irrelevant to whether two states merge?

Equivalence is defined by observable input/output behaviour, which conversion preserves; Mealy vs Moore Machines differ in when output appears, not in which states are indistinguishable.

Edge cases

If a machine has exactly one state, what does minimization return?

The same single state — it is trivially minimal, since there is no second state to be distinguishable from.

If every state produces the same output, what is

P_{0}

A single block containing all states — no output distinguishes anyone at length 0, so the first split (if any) must come from next-state behaviour at

P_{1}

Can two states be equivalent if one is reachable and the other is unreachable from the start state?

Yes, equivalence itself ignores reachability, but unreachable states should first be pruned — they never affect behaviour and needlessly inflate the table.

What happens if the initial state is inside a merged class?

The merged class becomes the new initial state; the start state is just relabelled to whichever block contains the original start.

Two states loop to themselves on every input with the same output — are they equivalent?

Yes. Each is a self-contained sink emitting one output forever; if their outputs match, no input string ever separates them.

A state's next state on some input is itself (a self-loop) — does that break the equivalence test?

No. The rule "

δ (p, x)

and

δ (q, x)

share a block" still applies; a self-loop just means

δ (p, x) = p

, and you check which block

p

currently sits in.

If refinement produces all singleton blocks, what does that mean?

The machine is already minimal — every state is distinguishable from every other, so nothing merges.

Two distinguishable states happen to be

k

-indistinguishable for a large

k

but split at

k + 1

— is that a problem?

No, that is normal. The algorithm keeps refining; distinguishability can appear at any length up to

N - 1

, and the loop only stops when a full pass adds no split.

Recall One-line summary to carry away

Merge only on Same-Out AND Same-Next, refine until nothing changes, count final blocks, and remember a merge helps logic even when it doesn't cross a $lo g_{2}$ boundary to save a flip-flop.