State equivalence minimization and encoding
Remove redundant history without changing behavior
Two states may have different names yet encode the same information needed for every future output. State minimization merges such states while preserving the specified observable behavior. This is not the same operation as assigning shorter binary names to states or simplifying a Boolean equation.
Prerequisites: Moore/Mealy machines, next-state tables, D flip-flops and combinational minimization. We use deterministic, fully specified machines, one binary input x, and Moore outputs observed in the current state, including the reset state. All transitions occur at valid rising edges. Incompletely specified machines and asynchronous state assignment require separate methods.
Two Moore states are equivalent if they produce the same current output and identical output sequences for every possible future input sequence. Matching only one trace is insufficient. A useful recursive criterion is: their current outputs match, and for every input their successor states are themselves equivalent. Equal output alone is necessary but not sufficient.
Reachability is relative to allowed starts
A state is reachable if some permitted input sequence takes an allowed starting state to it. Begin with reset state, repeatedly add successors of already found states, and stop when no new states appear. A state outside this set cannot affect normal traces from that reset under the stated input assumptions.
Removing an unreachable state is safe only for that behavior contract. If a fault-recovery requirement, another reset, a test mode or an allowed initial state can enter it, its behavior may still matter. “Unreachable” is not a general permission to ignore hardware startup or recovery specifications.
Worked machine
The following Moore machine resets to A. Output y is attached to the current state, not to a transition.
| State | y | Next on x=0 | Next on x=1 |
|---|---|---|---|
| A | 0 | C | D |
| B | 0 | C | E |
| C | 0 | C | C |
| D | 1 | B | D |
| E | 1 | A | E |
| F | 1 | F | F |
From A, input 0 reaches C and 1 reaches D. From D, 0 reaches B; from B, 1 reaches E. Thus A,B,C,D,E are reachable. F is not reached from any of them and is not a permitted start, so remove F from this normal-operation minimization. C is reachable and cannot be removed merely because it is a sink.
Partition refinement
Start by grouping states with the same current output. Here the initial partition is {A,B,C} and {D,E}. For each state, list the blocks containing its successors under input 0 and input 1. Split a block if its members have different successor-block lists. Repeat until no block splits.
In the first partition, A and B have signature (zero-output block, one-output block). C has signature (zero-output block, zero-output block), so split C away. D and E both have signature (zero-output block, one-output block) but stay separate from A,B because their current output is 1. Matching successor signatures never overrides an existing output distinction.
Now the blocks are U={A,B}, V={C}, W={D,E}. Their transitions are:
| Block | y | Next on 0 | Next on 1 |
|---|---|---|---|
| U | 0 | V | W |
| V | 0 | V | V |
| W | 1 | U | W |
Check stability: A and B both go to V on 0 and W on 1; D and E both go to U on 0 and W on 1. No further split is needed. This fixed-point partition gives equivalent-state classes for the fully specified Moore machine.
Why three states are necessary
U and W differ immediately in output 0 versus 1; V and W also differ immediately. U and V currently both output 0, but input 1 takes U to W with output 1 while V remains output 0. Thus the one-symbol sequence 1 distinguishes them. Every pair of the three blocks is distinguishable, proving no further merge can preserve behavior.
Worked trace: input sequence 1,0,1,0 takes the original machine A→D→B→E→A. The corresponding reduced trace is U→W→U→W→U. Including the initial output, both give 0,1,0,1,0. This trace illustrates the mapping; the stable-partition reasoning, not this single trace, is the general proof.
Encode the reduced machine and specify unused patterns
Three reduced states need at least two binary storage bits. Choose U=00,V=01,W=10 in Q_1Q_0. This choice is an encoding, not another minimization. For the unused pattern 11, specify next state V=01 and output 0. Reset selects U=00. Giving this recovery rule prevents a silent assumption that unused patterns may behave arbitrarily.
With D flip-flops, the next-state functions are
D_1=Q_0′x; D_0=Q_0+Q_1′x′; y=Q_1Q_0′.
Derive them from the complete eight-row table of four binary states times two inputs. For U=00, input 0 gives 01 and input 1 gives 10. For V=01, both inputs give 01. For W=10, input 0 gives 00 and input 1 gives 10. For 11, both inputs give 01 and y=0. These checks establish the required recovery as well as the valid-state behavior.
A one-hot encoding could instead assign one of three flip-flops to each state. It uses more state bits but may simplify some next-state logic. Fewer abstract states, fewer stored bits, fewer literals and shorter physical delay are different optimization objectives. A binary-minimal bit count does not prove a fastest circuit.
Mealy machines need output vectors
For a Mealy machine, outputs depend on input as well as state. Initially distinguish states whose output vectors differ for any input. Then refine using successor classes under every input, just as above. Comparing only a single output symbol without its input is not sufficient. State equivalence must preserve the same output observation convention; changing pre-edge outputs into registered post-edge outputs changes the interface contract.
Checking and common mistakes
List allowed starts before reachability; preserve any required recovery behavior. Partition first by observable outputs, then repeatedly by successor classes until stable. Produce a distinguishing sequence when rejecting a proposed merge. Build a quotient transition table, select an encoding, define every unused pattern and verify the resulting equations. Do not merge states just because their current outputs match, or just because their raw successors have different names: different names can belong to equivalent classes.
Original practice
These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.
C01. Two Moore states have equal current outputs. Is that alone sufficient for equivalence?
A. Yes, always B. No; all future input sequences must also produce matching outputs. C. Yes, if their names have the same length D. No states with different names can be equivalent
Answer: B
A is incorrect: future successors can produce different outputs.
B is correct: current equality is necessary but future behavior must match too.
C is incorrect: names are labels, not behavioral information.
D is incorrect: minimization exists precisely because differently named states can be equivalent.
C02. In the worked machine reset to A, F loops to itself and no reachable state transitions to F. Under the normal-operation contract, what may be done?
A. Remove F as unreachable. B. Remove C because it is a sink. C. Merge F with any state regardless of output. D. Assume all hardware faults are impossible.
Answer: A
A is correct: F has no allowed path from the stated reset.
B is incorrect: C is reached from A on input 0.
C is incorrect: merging must preserve behavior, not ignore outputs.
D is incorrect: reachability analysis under a model is not a physical fault guarantee.
C03. The reduced blocks U and V both output 0; U on input 1 goes to W with output 1, while V stays in V. Which sequence distinguishes U and V?
A. The empty sequence B. No sequence can distinguish them. C. The single input 1 D. Every sequence must have at least three inputs.
Answer: C
A is incorrect: their current outputs match.
B is incorrect: their specified successors already give a counterexample.
C is correct: after input 1 their outputs are 1 and 0.
D is incorrect: one input already suffices.
C04. Which stable partition is obtained for reachable A,B,C,D,E in the worked table?
A. {A,B,C},{D,E} B. {A,D},{B,E},{C} C. All five singleton blocks D. {A,B},{C},{D,E}
Answer: D
A is incorrect: C has a different successor-block signature from A,B.
B is incorrect: it merges states with different current outputs.
C is incorrect: A/B and D/E have matching output and successor-class behavior.
D is correct: the three blocks preserve outputs and are closed under the same successor-class choices.
C05. For D_1=Q_0′x, D_0=Q_0+Q_1′x′ and y=Q_1Q_0′, what happens at unused state Q_1Q_0=11 for either input?
A. Next 11, y=1 B. Next 01, y=0 C. Next 00, y=0 D. Next state is unspecified
Answer: B
A is incorrect: D_1=0 and y=0 because Q_0′=0.
B is correct: D_1=0,D_0=1,y=0 independently of x.
C is incorrect: D_0=1 because Q_0=1.
D is incorrect: the equations explicitly define both input cases.
C06. What is the correct relationship between state minimization and encoding?
A. Encoding always reduces the number of abstract states. B. One-hot encoding always uses the fewest bits. C. Minimization merges behaviorally equivalent states; encoding assigns bit patterns to the remaining states. D. The encoding with the fewest bits must have the shortest physical delay.
Answer: C
A is incorrect: renaming states as bits does not merge behavior.
B is incorrect: binary encoding can use fewer bits than one-hot.
C is correct: these are distinct design decisions with different purposes.
D is incorrect: bit count and timing depend on different circuit costs.
Scope and sources
This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.
Sources checked 14 October 2026.
Sign in to keep your progress. Sign in