5.5State minimisation
The idea
State minimisation merges states that behave identically, so the machine needs fewer states and flip-flops.
Think of it like this: Two employees who always answer every question the same way can be replaced by one.
Why it exists
GATE asks how many states remain after minimisation and how many flip-flops that needs.
How it works
- Group states by their outputs for each input.
- Split any group whose members go to different groups on some input.
- Repeat until no group splits.
- Merge each remaining group into one state.
Worked example: The 5-state example
Outputs separate {A, D, E} from {B, C}. Then A goes to {B,C}/{B,C} while D and E go to A, so A splits off. Result: {A}, {B,C}, {D,E}, three states instead of five.
Now play with it
- →Press Next step to watch the groups split.
- →Find which states look different but have the same next states.
| state | next/out on 0 | next/out on 1 |
|---|---|---|
| A | B / 0 | C / 1 |
| B | D / 0 | E / 0 |
| C | D / 0 | E / 0 |
| D | A / 0 | A / 1 |
| E | A / 0 | A / 1 |
- Group by output: {A,D,E} {B,C}
- Split by next-state groups (round 1): {A} {D,E} {B,C}
- Stable. Equivalent states merge: {A} {D,E} {B,C} → 3 states instead of 5
Two states are equivalent if for every input sequence they give the same outputs. Start with groups of equal outputs and keep splitting groups whose members lead to different groups; what survives can be merged. Fewer states means fewer flip-flops.
Check yourself
A sequential machine with 6 states reduces to 3 states after minimisation. The number of flip-flops needed changes from
Exam notes (the dense version)
Two states are equivalent if they produce the same output for every input and their next states are equivalent. Use partition refinement (or the implication table): first group states with identical outputs, then split any group whose members move to different groups, repeat until stable. Equivalent states are merged, which can reduce the number of flip-flops. In an incompletely specified machine compatible (not equivalent) states are merged, which is harder.
Previous year questions: Counters, Registers & State Machines (10)
PYQs are grouped by topic, so this is the full set for Counters, Registers & State Machines; try the ones that match this subtopic. Open all 10 on the topic page.