1.5Designing DFAs and counting states
The idea
To design a DFA, decide what the machine must remember, then give that memory a state each.
Think of it like this: Packing a suitcase: only take what you will need later.
Why it exists
GATE asks for the minimum number of states, so you need the patterns by heart.
How it works
- Ends with / contains a string of length m: remember how much of it you have matched: m + 1 states.
- Divisible by k or count mod k: remember the remainder: k states.
- Both of two conditions (AND/OR): product of the two machines: m × n states.
- Complement: swap final and non-final in a complete DFA.
Worked example: Binary numbers divisible by 3
Remainder after reading bits: r → (2r + bit) mod 3. Three states r0, r1, r2; r0 is final. For 110 (= 6): r0 → r1 → r0 → r0 ✓.
Now play with it
- →Run 110, 101 and 1001 on the divisible-by-3 machine.
- →Check the table: which pattern needs which number of states?
| Language over {a, b} | States in minimal DFA |
|---|---|
| ends with "ab" | 3 (length 2 + 1) |
| contains "aba" | 4 (length 3 + 1) |
| number of a's ≡ r (mod 3) | 3 |
| starts with "ab" | 4 (3 + one dead state) |
| third symbol from the end is a | 8 (2³) |
| length divisible by 4 | 4 |
| even a's AND even b's (product) | 4 (2 × 2) |
Use these as patterns, then check the question's exact wording (starts / ends / contains) and whether a dead state is counted.
- Start: ε-closure of r0 = {r0}
- read "1" → {r1}
- read "1" → {r0}
- read "0" → {r0}
- End of input and at least one active state is final: ACCEPT
Check yourself
Minimal DFA states for "strings over {a,b} that contain aba as a substring":
Exam notes (the dense version)
Think of what the machine must remember: the last few symbols (ends with / contains), a remainder (divisibility), or parity. Union and intersection of two DFAs use the product construction (m × n states). Complement = swap final and non-final in a complete DFA.
Previous year questions: Finite Automata (DFA, NFA, ε-NFA) (6)
PYQs are grouped by topic, so this is the full set for Finite Automata (DFA, NFA, ε-NFA); try the ones that match this subtopic. Open all 6 on the topic page.