Chapter recap
A DFA (Q, Σ, δ, q₀, F) has exactly one move per (state, symbol), reads each symbol once, and accepts iff it ends in F. δ̂ extends δ to strings; L(M) is the set of accepted strings; a language is regular if some DFA accepts it. Dead states make δ total and are counted in minimal-DFA questions. Design patterns: starts-with k+2, contains/ends-with k+1, length mod n → n, counts mod m and n → m·n, binary ÷k → k (fewer for even k). Product construction runs two DFAs in parallel (≤ m·n states) for ∩, ∪, −; complement = swap F in a complete DFA.
Merged rule card
From 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ⁿ.
From 1.1.2 Extended transition function and regular languages
- δ̂(q, ε) = q; δ̂(q, wa) = δ(δ̂(q, w), a); δ̂(q, xy) = δ̂(δ̂(q, x), y).
- L(M) = { w : δ̂(q₀, w) ∈ F }. Regular ⇔ accepted by some DFA. All finite languages are regular.
- From the graph: empty ⇔ no reachable final; Σ* ⇔ all reachable states final; infinite ⇔ cycle on a path start→final.
- Prove correctness with state meanings + induction on |w|.
From 1.1.3 DFA design patterns
| Language (|w| = k pattern) | Minimal states |
|---|---|
| starts with w | k + 2 |
| contains w / ends with w | k + 1 |
| |x| ≡ r mod n | n |
| |x| = k, |x| ≤ k | k + 2 |
| |x| ≥ k | k + 1 |
| #a mod m and/or #b mod n | m·n (typical) |
| binary value ≡ 0 mod k, k odd | k |
| binary ÷ 2ʲ | j + 1 |
| k-th symbol from start fixed | k + 2 |
Divisibility update: r ← (base·r + digit) mod k.
From 1.1.4 Product construction and complement
- Product: states Q₁×Q₂, δ((p,q),a) = (δ₁(p,a), δ₂(q,a)), start (s₁,s₂).
- ∩: F₁×F₂. ∪: F₁×Q₂ ∪ Q₁×F₂. −: F₁×(Q₂−F₂). ≤ |Q₁|·|Q₂| states.
- Complement: complete the DFA (add dead state), swap F ↔ Q−F; same state count.
- Regular languages closed under ∪, ∩, −, complement.
Practice questions
- NAT
Minimal DFA states over {0,1}: strings whose value in binary is divisible by 7?
Write your answer before opening the key.
- NAT
Minimal DFA states over {a,b}: strings of length exactly 3?
Write your answer before opening the key.
- MCQ
Which statement about complementing a DFA is correct?
- Swap F in any drawing
- Make it complete, then swap F
- Reverse all arrows
- Swap start and accepting states
- MSQ
Over {a,b}, which have a 4-state minimal DFA?
- starts with ab
- ends with aab
- |w| mod 4 = 1
- contains bbb
- NAT
Strings of length 4 over {a,b} accepted by the “even number of a’s” DFA?
Write your answer before opening the key.
- NAT
Minimal DFA states for binary numbers divisible by 8?
Write your answer before opening the key.
- MCQ
A DFA over {a,b} with start state p (non-accepting) and both transitions of p going to an accepting sink. L(M) = ?
- Σ*
- Σ⁺
- {ε}
- ∅
- NAT
Upper bound on states of the product DFA for (#a ≡ 0 mod 2) ∪ (#b ≡ 0 mod 5)?
Write your answer before opening the key.
Answer key
Reveal answers when you’re ready
- 7 — Odd divisor: all remainders needed.
- 5 — Counter 0..3 plus dead.
- B — Completeness is essential.
- A: Fails if the dead state is missing.
- C: That is reversal — a different language.
- D: Not the complement.
- ABCD — k+2 with k=2; k+1 with k=3; mod 4; k+1 with k=3.
- 8 — C(4,0)+C(4,2)+C(4,4) = 1+6+1 = 8.
- 4 — ÷2³ → j + 1 = 4 (it is “ends with 000”, plus handling).
- B — Every non-empty string ends in the sink; ε stays at p.
- A: ε is rejected.
- C: ε is the only rejected string.
- D: Most strings are accepted.
- 10 — 2 × 5.