Subset construction and the 2ⁿ blow-up

1. What is ECLOSE(q)?
   Stuck? Peek at 1.2.2 ε-NFA and ε-closure

   • ε-NFA: δ : Q × (Σ ∪ {ε}) → P(Q).
   • ECLOSE(q) = ε-reachable states incl. q (graph reachability on ε-edges).
   • Run: start ECLOSE(q₀); each symbol: move, then ECLOSE. Accept iff final set ∩ F ≠ ∅.
   • Same power as DFA/NFA; great for wiring machines together.

   Read lesson 1.2.2

2. When does an NFA accept?
   Stuck? Peek at 1.2.1 Nondeterminism and the NFA

   • NFA: δ : Q × Σ → P(Q); moves may be 0, 1, many.
   • Accept iff some path ends in F ⇔ δ̂(q₀, w) ∩ F ≠ ∅. Track the set of active states.
   • DFA ⊆ NFA; NFAs accept exactly the regular languages.
   • No dead state needed. Swapping F does NOT complement an NFA.

   Read lesson 1.2.1

3. How many subsets does a 4-element set have?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

Real hardware can’t clone itself at every fork, so an NFA can’t run as-is on a chip. But look at how we traced NFAs: we kept the set of active states. There are only finitely many such sets. So make each set a single state of a new machine — and that machine is deterministic. This conversion is called the subset construction, and GATE asks you to run it or to count its states.

An NFA has 3 states. At most how many states can the DFA produced by the subset construction have?

Prediction check

Answer: 2³ = 8 — one per subset of {q0, q1, q2}, including ∅ (which plays the role of the dead state). Usually far fewer are reachable.

The construction (NFA → DFA)

Proof idea: by induction on |w|, δ̂_D({q₀}, w) is exactly the active set of N after w. So D accepts w iff N’s active set contains an accepting state iff N accepts w.

Doing it by hand (lazy construction)

1. Write the start set. Put it in a worklist.
2. Take a set S from the worklist; for each symbol, compute the target set. Any new set goes into the worklist.
3. Repeat until no new sets appear.
4. Mark sets containing an NFA accepting state.
5. If ∅ appears, it is the dead state (it maps to itself).

ε-NFA → NFA (removing ε-moves)

Keep the same states. New δ'(q, a) = ECLOSE( ⋃_{p ∈ ECLOSE(q)} δ(p, a) ). New accepting set F' = { q | ECLOSE(q) ∩ F ≠ ∅ } — the start state can become accepting this way. The number of states does not change.

The 2ⁿ blow-up is real

Language L_k = “the k-th symbol from the end is 1”. NFA: k + 1 states. Any DFA: at least 2ᵏ states. Reason: take two different strings x, y of length k. They differ at some position i; append enough symbols so that position lands exactly k-th from the end: one becomes accepted, the other not. So all 2ᵏ strings of length k need different states.

So: NFA with n states ⇒ equivalent DFA with ≤ 2ⁿ states, and this bound can be (nearly) reached. NFAs can be exponentially more compact.

Counting DFA states in GATE questions

• “Subset construction on this NFA gives how many states?” — run the lazy construction; count only reachable sets; include ∅ if it appears.
• “Minimum DFA states for k-th from end is 1 over {0,1}” — 2ᵏ.
• “k-th from the start” — only k + 2 (Lesson 1.1.3). Don’t mix them up.

Putting it together

• Subset construction: a DFA state = a set of NFA states; accepting iff it meets F; ∅ is the dead state.
• At most 2ⁿ states; count only reachable sets.
• k-th from the end needs 2ᵏ DFA states; k-th from the start only k + 2.

NFA ends-with-ab:  q0 —a,b→ q0,  q0 —a→ q1,  q1 —b→ q2 (final)
writing states as numbers {0},{0,1},... :

 set S        on a                 on b
→{0}          {0,1}                {0}
 {0,1}        {0,1}                {0,2}
*{0,2}        {0,1}                {0}       ← contains 2 (final)
 3 reachable sets out of 2³ = 8 possible; ∅ never appears (q0 always active)

3rd-from-end NFA (q0..q3)  → reachable sets: every {0} ∪ X with X ⊆ {1,2,3}  = 2³ = 8 DFA states
each set records which of the last 3 symbols were 1:   {0,1,3} after ...1?1 etc.

DFA = NFA = ε-NFA in power. The subset construction can produce DFAs with redundant states — like {q1} and {q0,q1} above, which behave identically. Next chapter: how to detect and merge such states to get the minimal DFA, the single most frequent TOC question type in GATE.

1. NAT

   Minimal DFA states for strings over {0,1} whose 4th symbol from the end is 1?

   Write your answer before opening the key.

2. NAT

   Minimal DFA states for strings over {0,1} whose 4th symbol from the start is 1?

   Write your answer before opening the key.

3. MCQ

   In the subset construction, a DFA state S is accepting iff:

   1. S ⊆ F
   2. S ∩ F ≠ ∅
   3. S = F
   4. S contains q₀
4. MSQ

   An NFA has n states. Which are true?

   1. An equivalent DFA with at most 2ⁿ states exists
   2. Every equivalent DFA has at least 2ⁿ states
   3. Some languages need about 2ⁿ DFA states for an n-state NFA
   4. The subset construction always produces a minimal DFA
5. NAT

   Subset construction on the ends-with-ab NFA (3 states) yields how many reachable DFA states?

   Write your answer before opening the key.

• subset construction
• lazy (reachable-only) construction
• ε-removal
• exponential (2ⁿ) blow-up
• equivalent machines (same language)

1. Upper bound on DFA states from an n-state NFA?
   Reveal answer

   2ⁿ
2. Minimal DFA for “k-th symbol from the end is 1”?
   Reveal answer

   2ᵏ states.
3. Which subsets are accepting in the subset construction?
   Reveal answer

   Those containing at least one NFA accepting state.
4. What does ∅ become in the subset construction?
   Reveal answer

   The dead state.

• k-th from END → 2ᵏ. k-th from START → k + 2. Write “END = Exponential” on your hand.