A minimum-state question is not asking you to stare at a DFA until two states look similar. It is asking for a fixed partition-refinement algorithm. Remove unreachable states first, refine groups by transition behaviour, and stop only when no group splits.
Step 0: remove unreachable states
Start from the initial state and mark every state reachable by some input string. Any unmarked state can never participate in a run from the start, so it contributes nothing to the accepted language and must be deleted before minimization.
This is a silent exam trap. An unreachable final state is still unreachable. It does not need its own class in the minimal DFA.
For the worked example, consider this DFA over alphabet {0, 1}. State A is initial. States C and D are final.
State | Input 0 | Input 1 | Final? |
|---|---|---|---|
A | B | C | No |
B | A | D | No |
C | E | C | Yes |
D | E | D | Yes |
E | E | A | No |
F | F | F | No |
From A, input 0 reaches B and input 1 reaches C. From C, input 0 reaches E. From B, input 1 reaches D. Thus A, B, C, D and E are reachable. No transition from any of those states reaches F, so F is unreachable and is removed.
Do this reachability pass before counting partitions. Keeping F would give a wrong extra state even if every later refinement step were perfect.
Partition refinement, step by step
Two states may be merged only if no input string can distinguish them. Partition refinement tests that condition systematically.
Initial partition: 0-equivalence
The empty string already distinguishes a final state from a non-final state. Therefore, the initial partition P0 has two blocks:
P0 = {{C, D}, {A, B, E}}
Call {C, D} block F for final and {A, B, E} block N for non-final. Now write the destination block reached by 0 and 1 for every state.
State | Block on 0 | Block on 1 | Signature under P0 |
|---|---|---|---|
A | N | F | (N, F) |
B | N | F | (N, F) |
E | N | N | (N, N) |
C | N | F | (N, F) |
D | N | F | (N, F) |
Signatures are compared only among states already in the same block. A and B remain together because their signatures match. E must split from them because input 1 sends A and B to a final block but sends E to a non-final block. C and D remain together.
So the next partition is:
P1 = {{A, B}, {E}, {C, D}}
Refine again with the new blocks
Name the three blocks X = {A, B}, Z = {E}, and Y = {C, D}. Their letters are chosen to make the minimized transition table easy to read.
State | Block on 0 | Block on 1 | Signature under P1 |
|---|---|---|---|
A | X | Y | (X, Y) |
B | X | Y | (X, Y) |
E | Z | X | (Z, X) |
C | Z | Y | (Z, Y) |
D | Z | Y | (Z, Y) |
No block splits. A and B still have identical signatures, and C and D still have identical signatures. A singleton block cannot split. The partition is stable, so the algorithm stops.
The minimized DFA has three states:
Minimized state | Contains | Input 0 | Input 1 | Final? |
|---|---|---|---|---|
X | {A, B} | X | Y | No |
Y | {C, D} | Z | Y | Yes |
Z | {E} | Z | X | No |
The initial state is X because it contains A. The only final minimized state is Y because it contains C and D.
Reading and verifying the minimum-state answer
The number of blocks in the stable partition is the number of states in the minimal reachable DFA. Here that number is 3, not 5 and not 4.
A quick distinguishing-string check verifies that the three blocks cannot merge:
X and Y differ on the empty string, because Y is final and X is not.
Z and Y also differ on the empty string.
X and Z differ on input 1. From X, input 1 reaches final state Y and is accepted. From Z, input 1 reaches non-final state X and is rejected.
Within X, states A and B are not distinguished by any string because each input sends both into the same equivalence blocks. The same reasoning holds for C and D inside Y. This independent check agrees with the refinement table.
If you need to revisit the language recognised by states before minimizing them, Finite Automata: DFA vs NFA supplies the wider foundation. Then use Theory of Computation: Finite Automata MCQs to practise identifying equivalent states.
Myhill-Nerode in one paragraph
The Myhill-Nerode theorem says that strings are equivalent when appending any continuation gives the same accept-or-reject result for both. A regular language has finitely many such equivalence classes, and the number of classes is exactly the number of states in its unique minimal DFA, up to renaming. Partition refinement is the state-based version of this idea: states stay together only when no future suffix can distinguish them.
You do not need a long proof for most numericals. The useful conclusion is that the minimum is well-defined. A different-looking DFA for the same language cannot beat the number of distinguishable classes.
How GATE tests DFA minimization
The direct forms ask for the number of states after minimization or which named states merge. Variants first complement a DFA, combine two automata through a product construction, or include an unreachable state among plausible answers.
Common mistakes are beginning with one block instead of final versus non-final, comparing destinations by state name instead of current block, stopping after the first split, and forgetting reachability. For the current syllabus and official exam-specific instructions, consult the official GATE portal of the organising IIT. GATE CS Exam Preparation Courses & Test Series places Theory of Computation within the full preparation path.
The short version and next step
Delete unreachable states. Split reachable states into final and non-final blocks. Repeatedly give every state a transition signature based on the current blocks, split unequal signatures, and stop when the partition is stable. The stable block count is the minimum state count.
The KnowledgeGate bank contains about 1,000 published Theory of Computation questions. Once you can reproduce the worked split without help, use the GATE Test Series to practise the same algorithm inside less obvious question wording.
