Partition and table-filling methods

1. How is ≡ₖ₊₁ obtained from ≡ₖ?
   Stuck? Peek at 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.

   Read lesson 1.3.1

2. Subset construction: which sets are accepting?
   Stuck? Peek at 1.2.3 Subset construction and the 2ⁿ blow-up

   • Subset construction: start {q₀} (or ECLOSE(q₀)); δ(S,a) = ⋃ δ(q,a) (then ECLOSE); accept iff S ∩ F ≠ ∅; ∅ = dead state.
   • ≤ 2ⁿ states; count only reachable sets.
   • ε-removal: δ'(q,a) = ECLOSE(δ(ECLOSE(q), a)); F' = {q : ECLOSE(q) ∩ F ≠ ∅}.
   • k-th from end is 1: NFA k+1, DFA 2ᵏ. k-th from start: DFA k+2.
   • DFA ≡ NFA ≡ ε-NFA in power.

   Read lesson 1.2.3

3. Minimal DFA for #a ≡ 0 (mod 2) and #b ≡ 0 (mod 3)?
   Stuck? Peek at 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.

   Read lesson 1.1.3

In the exam you have about three minutes per 2-mark question. You need a procedure that never misses a merge and never merges wrongly. Two such procedures exist; both compute the same equivalence classes. Learn the partition method for speed, and the table-filling method because GATE sometimes asks about “pairs of distinguishable states”.

A DFA has 7 states after removing unreachable ones; 3 are accepting. What is the smallest and largest number of states its minimal DFA could have?

Prediction check

Smallest: 2 — accepting and non-accepting states can never merge, so at least one class of each (when both exist). Largest: 7 — nothing merges.

Method 1 — partition refinement (Moore / Hopcroft style)

1. Remove unreachable states.
2. P₀ = {F, Q − F}.
3. For each group, write every state’s “signature”: the group each symbol sends it to.
4. Split each group by signature. That gives P₁.
5. Repeat until a round changes nothing. The groups are the minimal DFA’s states.

Tip: write the signature as a short tuple like (II, I) meaning “0 → group II, 1 → group I”.

Method 2 — table filling (Myhill table)

1. Draw a triangle table with one cell per unordered pair {p, q}.
2. Mark every pair with exactly one accepting state (distinguished by ε).
3. Repeat: for each unmarked pair {p, q} and each symbol a, if {δ(p,a), δ(q,a)} is marked, mark {p, q}.
4. Stop when a full pass marks nothing. Unmarked pairs are equivalent.

Number of cells = n(n−1)/2. Marked = distinguishable pairs; unmarked = equivalent pairs.

Reading the minimal DFA

Each class is a state; the class containing q₀ is the start; classes inside F are accepting; transitions: pick any member, follow its arrow, see which class it lands in.

Counting without drawing: the “distinct futures” method

For “minimal DFA for language L” questions, list the different situations a prefix can leave you in — situations that differ in which continuations are accepted. Each different situation = one state. Don’t forget the hopeless situation (dead state) and the “already satisfied” situation.

Putting it together

• Partition method: split by signatures until a round changes nothing.
• Table filling: mark (F, non-F), propagate marks through successor pairs; unmarked pairs merge.
• Fast counting: list the different futures, then add a dead state if some prefix is hopeless.

Table filling on the 1.3.1 DFA (reachable states A..F, F_acc = {C,D,E})

     A    B    C    D    E
 B   ·                          ✗ = distinguishable  · = equivalent
 C   ✗    ✗                     pass 0: mark every (accepting, non-accepting) pair
 D   ✗    ✗    ·                pass 1: {A,F}: on 1 → {C,F} marked → mark ✗
 E   ✗    ✗    ·    ·                   {B,F}: on 1 → {D,F} marked → mark ✗
 F   ✗    ✗    ✗    ✗    ✗              {A,B}: on 0 → {B,A}, on 1 → {C,D}: unmarked → leave
                                pass 2: nothing new → stop
unmarked: {A,B}, {C,D}, {C,E}, {D,E}  → classes {A,B}, {C,D,E}, {F} → 3 states

We now minimize any given DFA. But what if you’re given only a language? The next lesson defines the equivalence classes directly on strings — no machine needed — and it gives the deepest characterization of regular languages: finite memory = finitely many classes.

1. NAT

   Table filling on an n-state DFA uses how many cells when n = 6?

   Write your answer before opening the key.

2. NAT

   Minimal DFA states over {a,b} for strings with at least 2 a’s?

   Write your answer before opening the key.

3. NAT

   Minimal DFA states over {a,b} for strings with exactly 2 a’s?

   Write your answer before opening the key.

4. MCQ

   In the partition method, P₀ is:

   1. {Q}
   2. {F, Q − F}
   3. one block per state
   4. { {q₀}, Q − {q₀} }
5. MSQ

   Over {a,b}, which languages have a minimal DFA with exactly 4 states?

   1. strings with at most 2 a’s
   2. strings with exactly 2 a’s
   3. strings ending in aba
   4. strings of length ≡ 0 mod 4

• partition refinement method
• signature of a state
• table-filling (Myhill) method
• distinguishable pair
• distinct futures counting

1. Minimal DFA for “exactly k a’s” over {a,b}?
   Reveal answer

   k + 2 states (0..k and dead).
2. Minimal DFA for “at least k a’s”?
   Reveal answer

   k + 1 states.
3. Minimal DFA for “at most k a’s”?
   Reveal answer

   k + 2 states (0..k accepting, plus dead).
4. How many cells in a table-filling table for n states?
   Reveal answer

   n(n−1)/2
5. When do you stop the partition method?
   Reveal answer

   After a full round in which no group splits.

• Count “situations”, not arrows: write the list of different futures a prefix can have. Each = one state. Then ask: is there a hopeless situation? (+1 dead.)
• Exactly k → k+2, at least k → k+1, at most k → k+2. “Exactly” and “at most” both need the dead state.