ε-NFA and ε-closure

1. When does an NFA reject a string?
   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

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

3. What is the reachable set from a node in a graph and how is it computed?
   Stuck? Peek at 0.2.5 Directed graphs

   • Directed graph (V, E ⊆ V×V); self-loop; in/out-degree; labelled edges spell words along paths.
   • Path length = #edges. Cycle = path returning to start. Self-loop = cycle of length 1.
   • Reachable set: grow from u until nothing new (BFS). Shortest path in n-node graph ≤ n−1 edges.
   • Infinitely many u→v paths ⇔ some cycle lies on a u→v route.

   Read lesson 0.2.5

You have one machine for “even number of a’s” and another for “b’s in multiples of three”. You want a machine for “either”. With an NFA you could carefully merge the start states. Easier: add a new start state with two free jumps — one into each machine — that read nothing. Free jumps are called ε-moves, and they turn machine-building into Lego.

In the ε-NFA for a*b* below, before reading anything, which states can the machine already be in?

Prediction check

Answer: {p, q}. It starts in p and can take the free ε-jump to q without reading. That set is the ε-closure of p. Because q is accepting, ε is accepted.

ε-moves

ε-closure

Compute it exactly like reachability in a graph (0.2.5), using only ε-edges: start with {q}, keep adding ε-successors until nothing new appears.

How an ε-NFA runs

1. Start set = ECLOSE(q₀).
2. On symbol a: move every active state on a (ignore ε here), take the union, then take ECLOSE of the result.
3. Accept iff the final set contains an accepting state.

Formally δ̂(q, ε) = ECLOSE(q); δ̂(q, wa) = ECLOSE( ⋃_{p ∈ δ̂(q,w)} δ(p, a) ).

Same power again

Every ε-NFA can be converted to an NFA without ε-moves (and then to a DFA). ε-NFAs still accept exactly the regular languages. Their value is in construction: union, concatenation and repetition of machines become one-line ε-wirings — the basis of converting regular expressions to automata in Phase 2.

Putting it together

• ε-moves change state without reading input.
• ECLOSE(q) = ε-reachable states including q; take it at the start and after every symbol.
• ε-NFAs accept exactly the regular languages.

a*b*:   p (a-loop) ──ε──► q (b-loop, accepting)
ECLOSE(p) = {p, q}     ECLOSE(q) = {q}
trace "aab": {p,q} ─a→ ECLOSE({p}) = {p,q} ─a→ {p,q} ─b→ ECLOSE({q}) = {q}   q ∈ F ACCEPT
trace "ba" : {p,q} ─b→ {q} ─a→ ∅                                           REJECT

We have three machine types — DFA, NFA, ε-NFA. Next lesson proves they are equally powerful by converting each into a DFA, and shows the price: the DFA can need up to 2ⁿ states.

1. MCQ

   ECLOSE(q) is:

   1. states reachable from q by any moves
   2. states reachable from q by ε-moves only, including q
   3. states reachable from q by exactly one ε-move
   4. the accepting states
2. NAT

   ε-NFA: 1 ─ε→ 2, 2 ─ε→ 3, 3 ─ε→ 1, 3 ─a→ 4. |ECLOSE(2)| = ?

   Write your answer before opening the key.

3. MSQ

   For the 0*1*0* ε-NFA in the GATE example, which strings are accepted?

   1. 000
   2. 101
   3. 1001
   4. 0110
4. MCQ

   An ε-NFA accepts ε exactly when:

   1. q₀ ∈ F
   2. ECLOSE(q₀) ∩ F ≠ ∅
   3. F = ∅
   4. it has an ε-move

• ε-move
• ε-NFA
• ε-closure ECLOSE(q)

1. ECLOSE(q) includes q?
   Reveal answer

   Yes, always (zero ε-moves).
2. How does an ε-NFA process a symbol?
   Reveal answer

   Move all active states on the symbol, union the results, then take the ε-closure.
3. When does an ε-NFA accept ε?
   Reveal answer

   When ECLOSE(q₀) contains an accepting state.