Unreachable, equivalent and distinguishable states

1. Minimal DFA states for “3rd from the end is 1”?
   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

2. What three properties make an equivalence relation?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

3. Minimal DFA states for “starts with a” over {a,b}?
   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

Two employees in an office handle requests identically: whatever comes in, they make the same final decision. You don’t need both on the org chart — merge them. In a DFA, two states that lead to the same accept/reject verdict for every possible future input are interchangeable. Finding and merging them gives the smallest possible DFA, and “how many states in the minimal DFA?” is GATE’s favorite TOC question.

In the DFA below, states C, D and E are all accepting, and each one goes to F (the dead state) on 1. Do you think C, D, E can be merged into one?

Prediction check

Answer: yes. From each of C, D, E: reading 0 keeps you in an accepting state (E), reading 1 kills you (F). Every future string gets the same verdict from all three. They are equivalent.

Step 0: remove unreachable states

A state is unreachable if no input leads to it from q₀ (no path in the graph). It never affects the language. Find reachable states by BFS from q₀ (Lesson 0.2.5); delete the rest. Always do this first — an unreachable state can look “distinct” and inflate your count.

Equivalent states

“Same verdict on every future.” ≡ is an equivalence relation (reflexive, symmetric, transitive), so it partitions Q into classes (Lesson 0.2.2). Each class becomes one state of the minimal DFA.

Distinguishable states

• ε distinguishes every accepting state from every non-accepting one.
• If δ(p, a) and δ(q, a) are distinguishable by w, then p and q are distinguishable by aw. This is how distinguishability spreads backwards.

k-equivalence

p ≡ₖ q means no string of length ≤ k distinguishes them.

• ≡₀ has two classes: F and Q − F.
• p ≡ₖ₊₁ q iff p ≡ₖ q and for every symbol a, δ(p, a) ≡ₖ δ(q, a).

Each round can only split classes. When a round splits nothing, it never will again: ≡ₖ = ≡. With n states this happens within n − 2 rounds.

The minimal DFA

Merge each equivalence class into one state; transitions go class to class (well-defined because equivalent states move to equivalent states). The result is the minimal DFA: no DFA for the language has fewer states, and it is unique up to renaming states.

Putting it together

• Remove unreachable states first.
• Equivalent states have identical futures; distinguishable ones are separated by some string.
• Refine {F, Q−F} until stable; each class is one state of the unique minimal DFA.

Step 0  reachable from A: {A,B,C,D,E,F}.  G is unreachable → delete.
≡₀ :  {A,B,F}  |  {C,D,E}                 (non-accepting | accepting)
≡₁ :  A: 0→B(N) 1→C(Y)   B: 0→A(N) 1→D(Y)   F: 0→F(N) 1→F(N)
      → split {A,B} | {F};   C,D,E: 0→E(Y) 1→F(N) → stay together
      {A,B} | {F} | {C,D,E}
≡₂ :  A: 0→B∈{A,B} 1→C∈{CDE};  B: 0→A∈{A,B} 1→D∈{CDE}  → same
      nothing splits → STOP.   3 classes = 3 states

Language: 0*10* (exactly one 1). Trace “0010”: AB→AB→AB→CDE→CDE accept. “0101”: AB→CDE→CDE→F reject.

We have the idea and the round-by-round splitting. Next lesson turns it into two exam-ready procedures — the partition method and the table-filling method — and drills the “number of states in the minimal DFA” question.

1. MCQ

   Two states p, q of a DFA are equivalent iff:

   1. they have the same outgoing labels
   2. for every w, δ̂(p,w) ∈ F ⇔ δ̂(q,w) ∈ F
   3. they are both accepting
   4. they are reachable from each other
2. MSQ

   Which are true?

   1. ε distinguishes an accepting state from a non-accepting state
   2. Unreachable states must be removed before minimizing
   3. If δ(p,a) and δ(q,a) are distinguishable then p and q are distinguishable
   4. Two accepting states are always equivalent
3. NAT

   Unary DFA: cycle 0→1→2→3→0 on a, start 0, F = {0, 2}. Minimal DFA states?

   Write your answer before opening the key.

4. MCQ

   Partition ≡₀ always consists of:

   1. one class
   2. F and Q − F
   3. one class per state
   4. reachable and unreachable states

• unreachable state
• equivalent states p ≡ q
• distinguishable states
• distinguishing string
• k-equivalence ≡ₖ
• minimal DFA (unique)

1. First step of minimization?
   Reveal answer

   Remove unreachable states.
2. When are two DFA states equivalent?
   Reveal answer

   Every string leads both to acceptance or both to rejection.
3. ≡₀ partition?
   Reveal answer

   {F, Q − F}
4. Is the minimal DFA unique?
   Reveal answer

   Yes, up to renaming states.