Chapter recap
NFAs allow 0, 1 or many moves per symbol (δ : Q × Σ → P(Q)); a string is accepted if some path ends in F. ε-NFAs also allow moves on ε; ECLOSE(q) collects ε-reachable states, taken at the start and after every symbol. DFA, NFA and ε-NFA accept exactly the same languages (the regular ones). The subset construction turns an n-state NFA into a DFA with ≤ 2ⁿ (reachable) subset-states; the bound is tight for “k-th from the end”. Swapping F complements DFAs (complete ones) but not NFAs.
Merged rule card
From 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.
From 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.
From 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.
Practice questions
- NAT
Minimal DFA for strings over {a,b} whose 2nd symbol from the end is a?
Write your answer before opening the key.
- MCQ
Which machine model can complement its language just by swapping accepting states (after completion)?
- NFA
- ε-NFA
- DFA
- none
- MSQ
ε-NFA: 1 ─ε→ 2, 2 ─a→ 3, 3 ─ε→ 1, F = {3}. Which strings are accepted?
- ε
- a
- aa
- aaa
- NAT
An NFA has 5 states. Maximum possible number of states of the subset-construction DFA?
Write your answer before opening the key.
- MCQ
Removing ε-moves from an ε-NFA with n states gives an NFA with:
- n states
- 2ⁿ states
- n + 1 states
- n² states
- NAT
NFA over {0,1} for “ends with 101” has a minimal number of states equal to?
Write your answer before opening the key.
- MSQ
Which are equal in power?
- DFA
- NFA
- ε-NFA
- DFA with two accepting states
- MCQ
Subset construction on an NFA where q₀ has a self-loop on every symbol: can ∅ appear as a DFA state?
- Yes, always
- No, q₀ is always active
- Only if F is empty
- Only for ε-NFAs
Answer key
Reveal answers when you’re ready
- 4 — 2².
- C — Determinism: one run, one final state.
- A: Multiple paths break it.
- B: Same issue.
- D: DFAs can.
- BCD — Language a⁺.
- A: ECLOSE(1) = {1,2}, no accepting state.
- 32 — 2⁵.
- A — Same states, new transitions and accepting set.
- B: That is the DFA bound.
- C: No new states needed.
- D: No.
- 4 — q0 (loop), then 1, 0, 1 → k + 1 = 4.
- ABCD — All accept exactly the regular languages.
- B — Every reachable set contains q₀.
- A: q₀ stays active.
- C: Unrelated.
- D: Unrelated.