L1.3 · DFA minimization

Chapter recap

Minimization: (1) delete unreachable states; (2) split {F, Q−F} repeatedly by where each symbol leads (partition method), or mark distinguishable pairs in a triangle table (table filling); (3) merge classes. The minimal DFA is unique. Myhill–Nerode groups strings by future: L is regular iff there are finitely many groups, and the number of groups is the minimal state count (dead class included). Count states fast by listing distinct situations. Exactly k → k+2, at least k → k+1, at most k → k+2.

Merged rule card

From 1.3.1 Unreachable, equivalent and distinguishable states

Step 0: delete unreachable states (BFS from q₀).
p ≡ q ⇔ ∀w: δ̂(p,w) ∈ F ⇔ δ̂(q,w) ∈ F. Distinguishable ⇔ some w separates.
≡₀ = {F, Q−F}; ≡ₖ₊₁ splits by where symbols lead w.r.t. ≡ₖ; stop when stable.
Merge classes → minimal DFA, unique up to renaming.

From 1.3.2 Partition and table-filling methods

Partition: remove unreachable; P₀ = {F, Q−F}; split by signatures w.r.t. previous partition; stop when stable.
Table filling: n(n−1)/2 cells; mark (F, non-F); propagate “successor pair marked ⇒ mark”; unmarked = equivalent.
Count by distinct futures: list situations with different accepted continuations, include dead / satisfied states.
Exactly k of a symbol: k + 2 states; at least k: k + 1; at most k: k + 2.

From 1.3.3 Myhill–Nerode theorem

x ≡_L y ⇔ ∀z: xz ∈ L ⇔ yz ∈ L. Right-invariant equivalence.
L regular ⇔ finite index; index = #states of minimal DFA (incl. dead class).
Infinitely many pairwise distinguishable strings ⇒ not regular. aⁿbⁿ: strings aⁱ separated by bⁱ.

Practice questions

NAT
Minimal DFA states over {0,1} for strings in which the number of 0s is even and the number of 1s is even?
Write your answer before opening the key.
NAT
Minimal DFA states over {a} for { aⁿ : n ≠ 2 }?
Write your answer before opening the key.
MCQ
A DFA has 8 reachable states, of which 0 are accepting. Its minimal DFA has:
1. 8 states
2. 1 state
3. 2 states
4. 0 states
MSQ
Which pairs are always distinguishable?
1. an accepting and a non-accepting state
2. two states whose a-successors are distinguishable
3. two accepting states
4. a reachable and an unreachable state
NAT
Minimal DFA states over {a,b} for strings where every a is immediately followed by b?
Write your answer before opening the key.
NAT
Index of ≡_L for L = { w ∈ {a,b}* : |w| ≤ 2 }?
Write your answer before opening the key.
MCQ
Which language is NOT regular (infinitely many Myhill–Nerode classes)?
1. { aⁿ : n is even }
2. { aⁿbᵐ : n, m ≥ 0 }
3. { aⁿbⁿ : n ≥ 0 }
4. { w : w ends with ba }
NAT
Minimal DFA states over {0,1} for strings that contain 01 or end with 1?
Write your answer before opening the key.

Answer key

Reveal answers when you’re ready

4 — 2 × 2 grid.
4 — Counts 0, 1, 2 (reject), ≥3 (accept sink): 0 vs ≥3 differ by z = aa? 0·aa = aa ∉ L, aaa·aa ∈ L. So 4.
B — L = ∅; one non-accepting state with self-loops.
- A: All states are equivalent.
- C: No accepting class exists.
- D: A DFA has at least one state.
AB — ε, or the extended separating string.
- C: May be equivalent.
- D: Reachability is not about verdicts.
3 — Free (last not a pending), pending (just read a, need b), dead. Accept: free.
4 — Lengths 0, 1, 2, ≥3 (dead).
C — aⁱ separated by bⁱ.
- A: 2 classes.
- B: a*b*: 3 classes.
- D: 3 classes.
4 — Strings with no 01 look like 1*0*. Classes: [ε]; [1⁺] (accepted, ends with 1); [1*0⁺] (rejected now, but any later 1 creates 01); [contains 01] (accept forever). ε vs 1⁺0⁺ is separated by z = 10 (“10” ∉ L but “010” ∈ L); ε vs 1⁺ by z = ε; 1⁺ vs “contains 01” by z = 0. Total 4.