DFA design patterns

1. When does a DFA accept ε?
   Stuck? Peek at 1.1.1 States and the DFA

   • DFA = (Q, Σ, δ, q₀, F), δ : Q × Σ → Q total. One step per symbol; always halts.
   • Accept iff the last state ∈ F. ε accepted ⇔ q₀ ∈ F.
   • Dead state: non-accepting, all self-loops. GATE counts it in minimal-DFA questions.
   • Exactly one string of length k: k + 2 states. #DFAs (n states, m symbols, fixed start) = nⁿᵐ · 2ⁿ.

   Read lesson 1.1.1

2. How many DFAs with 2 states over {a,b} with fixed start?
   Stuck? Peek at 1.1.1 States and the DFA

   • DFA = (Q, Σ, δ, q₀, F), δ : Q × Σ → Q total. One step per symbol; always halts.
   • Accept iff the last state ∈ F. ε accepted ⇔ q₀ ∈ F.
   • Dead state: non-accepting, all self-loops. GATE counts it in minimal-DFA questions.
   • Exactly one string of length k: k + 2 states. #DFAs (n states, m symbols, fixed start) = nⁿᵐ · 2ⁿ.

   Read lesson 1.1.1

3. If 11 numbers are divided by 5, must two share a remainder?
   Stuck? Peek at 0.2.4 Pigeonhole principle

   • n + 1 objects in n boxes ⇒ some box has ≥ 2.
   • N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
   • Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.

   Read lesson 0.2.4

GATE rarely asks you to invent a strange DFA. It asks: “how many states does the minimal DFA for this kind of language have?” — starts with, ends with, contains, length conditions, counts mod n, divisibility. Each kind has a standard shape and a state-count formula. Learn the shapes once and these questions take under a minute.

Over {a,b}: how many states does the minimal DFA need for “strings that contain aba”? And for “strings that start with aba”?

Prediction check

Contains aba: 4 (progress 0,1,2,3 matched letters; the last state accepts forever — no dead state needed). Starts with aba: 5 (progress 0..3 plus a dead state for a wrong start). The dead state is the difference.

Pattern 1 — starts with w (|w| = k)

States: progress 0, 1, …, k (k is accepting and loops on everything) plus a dead state for any mismatch. k + 2 states.

Pattern 2 — contains w as a substring

States: “longest prefix of w matched so far” 0, …, k. On a mismatch you don’t restart from 0 blindly: you move to the longest prefix of w that is a suffix of what you just read (contains aba: in state 2 = “ab”, reading b gives “abb”, whose longest suffix that is a prefix of aba is ε → state 0; reading a goes to 3). State k accepts and loops. k + 1 states. No dead state.

Pattern 3 — ends with w

Same “longest prefix of w that is a suffix of the input” states 0, …, k, but state k does not loop — further symbols can leave it. k + 1 states. (Ends with 01: 3 states, as in 1.1.2.)

Pattern 4 — length conditions

• |w| ≡ r (mod n): a cycle of n states, one per remainder.
• |w| = k exactly: k + 2 (counter 0..k, plus “too long” dead).
• |w| ≤ k: k + 2 (0..k accepting, then dead).
• |w| ≥ k: k + 1 (0..k, last one accepting with self-loop).

Pattern 5 — counting symbols mod m and n

“#a ≡ i (mod m) and #b ≡ j (mod n)”: a grid of states (#a mod m, #b mod n) → m · n states. The same grid works for “or”, “not”, any combination — only F changes. Minimal for most conditions (a condition that ignores one coordinate collapses it).

Pattern 6 — divisibility of numbers

Read a binary number left to right. If the value so far is v, reading bit b gives 2v + b. Track only r = v mod k: new r = (2r + b) mod k. So k states, start and accept at r = 0. For decimal: new r = (10r + d) mod k.

k states always suffice; the minimal number can be smaller when k shares factors with the base. Binary, divisible by 2: 2 states; by 4: 3 states (it is just “ends with 00”); by 8: 4 states; by 6: 4 states. For odd k in binary, all k remainder states are needed.

Pattern 7 — the k-th symbol from the start

“3rd symbol is 1”: skip 2 symbols (states 0,1,2), then 1 → accept-forever, 0 → dead. k + 2 states. (The k-th symbol from the end is a very different story — Chapter 1.2.)

Putting it together

• Starts-with: k + 2. Contains / ends-with: k + 1, with fall-back moves.
• Length mod n: n states. Two counters mod m and n: an m × n grid.
• Binary ÷ k: r ← (2r + b) mod k; minimal m + j for k = 2ʲ·m.

contains aba — failure moves explained
state = longest prefix of "aba" that is a suffix of what was read
 q0 ""   a→q1 "a"        b→q0
 q1 "a"  a→q1 "a" (aa: suffix "a")   b→q2 "ab"
 q2 "ab" a→q3 "aba" ✓    b→q0 (abb: no suffix is a prefix of aba)
 q3      a,b→q3 (already found)
traces: "babab": q0 b q0 a q1 b q2 a q3 b q3  ACCEPT
        "abba" : q0 a q1 b q2 b q0 a q1        REJECT

divisible by 3: r' = (2r + b) mod 3        trace 110 (=6): r0 ─1→ r1 ─1→ r0 ─0→ r0  ACCEPT
        0    1                                trace 111 (=7): r0 ─1→ r1 ─1→ r0 ─1→ r1  REJECT
→*r0    r0   r1
  r1    r2   r0
  r2    r1   r2         (ε stays in r0 and is accepted — by convention ε has value 0)

We now design single DFAs fast. But GATE often combines conditions: “even a’s AND ends with b”, “starts with a OR has odd length”. Next lesson builds DFAs for combinations automatically, by running two DFAs side by side — and flips a DFA to get its complement.

1. NAT

   Minimal DFA states over {a,b} for strings that start with abb?

   Write your answer before opening the key.

2. NAT

   Minimal DFA states over {a,b} for strings that end with abb?

   Write your answer before opening the key.

3. NAT

   Minimal DFA states for binary numbers divisible by 5?

   Write your answer before opening the key.

4. MSQ

   Which languages over {a,b} have a minimal DFA with exactly 3 states?

   1. |w| ≡ 0 (mod 3)
   2. w ends with ab
   3. |w| = 1
   4. w contains bb
5. MCQ

   Minimal DFA states for “#a ≡ 1 (mod 4) and #b ≡ 2 (mod 3)” over {a,b}:

   1. 7
   2. 12
   3. 4
   4. 3

• DFA design patterns
• failure transition (longest suffix that is a prefix)
• remainder states (mod n)
• grid / counter DFA (m·n states)
• divisibility DFA r ← (2r+b) mod k

1. Minimal states: strings starting with a fixed w, |w| = k?
   Reveal answer

   k + 2
2. Minimal states: strings containing w (|w| = k)?
   Reveal answer

   k + 1
3. Minimal states: binary numbers divisible by 4?
   Reveal answer

   3 (it is “ends with 00”)
4. Divisibility-by-k DFA transition for binary?
   Reveal answer

   r ← (2r + b) mod k
5. #a mod m and #b mod n — states?
   Reveal answer

   m · n

• Binary divisible by k = 2ʲ·m (m odd): the minimal DFA has m + j states. ÷6 → 3 + 1 = 4, ÷12 → 3 + 2 = 5, ÷8 → 1 + 3 = 4.
• For “contains w” the accept state is a sink; for “ends with w” it is not — that single difference is everything.