Extended NFA with Free Moves — Same Power, More Convenience
CS305 — Formal Language Theory
Arrow keys to navigate
All three models recognize exactly the same class of languages: the regular languages.
Adding ε-transitions does NOT increase the machine’s power. It only makes designing automata easier and more modular.
A DFA is like assembly — precise but tedious. An ε-NFA is like Python — higher-level, more expressive, but compiles down to the same computation.
Every conversion is possible:
Sometimes designing an NFA for a complex language is painful. We want to:
ε-transitions are LEGO connectors: snap small, tested components together into bigger machines without redesigning anything.
An ε-transition allows the machine to change state without reading any input symbol. The machine “spontaneously” moves.
ε is not a symbol in the alphabet Σ. It’s a special marker meaning “no input.”
An ε-NFA is E = (Q, Σ, δ, q0, F) where:
| Component | Meaning |
|---|---|
| Q | Finite set of states |
| Σ | Input alphabet (ε ∉ Σ) |
| δ | Q × (Σ ∪ {ε}) → P(Q) |
| q0 | Start state (q0 ∈ Q) |
| F | Accept states (F ⊆ Q) |
NFA: δ : Q × Σ → P(Q)
ε-NFA: δ : Q × (Σ ∪ {ε}) → P(Q)
The transition function now also accepts ε as input. The transition table gets an extra column for ε.
| a | b | ε | |
|---|---|---|---|
| → q0 | ∅ | ∅ | {q1} |
| q1 | {q2} | ∅ | ∅ |
| *q2 | ∅ | ∅ | ∅ |
The ε column is new — it tells us where the machine can go for free.
ε is never in the alphabet. The transition function’s domain is extended to include ε, but Σ stays the same.
Build an ε-NFA for L = { strings over {a,b} that start with ‘a’ or end with ‘b’ or are empty }.
| a | b | ε | |
|---|---|---|---|
| → *q0 | ∅ | ∅ | {q1, q3} |
| *q1 | {q2} | ∅ | ∅ |
| *q2 | {q2} | {q2} | ∅ |
| q3 | {q3} | {q3, q4} | ∅ |
| *q4 | ∅ | ∅ | ∅ |
q1-q2 handles “starts with a”. q3-q4 handles “ends with b”. q0 uses ε to choose which sub-machine to enter.
The ε-closure of state q is the set of all states reachable from q by following zero or more ε-transitions.
CL(q) is the smallest set such that:
Each ε-transition is a wormhole. CL(q) is everywhere you can reach from q using only wormholes (no fuel needed). You always include your starting location!
A state is always in its own ε-closure. CL(q) always contains q itself.
Click a state to watch BFS discover its ε-closure step by step.
ε-closure is just graph reachability. The ε-transitions form a directed graph; CL(q) = all nodes reachable from q.
We often need the ε-closure of a set of states, not just one state.
For a set of states S ⊆ Q:
CL(S) = ⋃q ∈ S CL(q)
Just take the union of every individual ε-closure.
After each “real” step (reading a symbol), all your tokens teleport through every wormhole they can reach. You always “expand” via ε before and after reading input.
Tells us the set of states reachable from q after reading string w, with ε-closures baked in.
Base case:
δ̂(q, ε) = CL(q)
On empty input, reach anything via ε.
Inductive case: For w = xa:
δ̂(q, xa) = CL( ⋃p ∈ δ̂(q,x) δ(p, a) )
Process x to get states, follow ‘a’ from each, then ε-close the result.
In a plain NFA: δ̂(q, ε) = {q}.
In ε-NFA: δ̂(q, ε) = CL(q), which may include many states!
ε-NFA for L = {“ab”} ∪ {“b”}: type a string and step through processing.
ε: q0→{q1,q4} | a: q1→q2 | b: q2→q3, q4→q5 | F={q3,q5}
ε-edges: p→q, p→s, q→r, s→t, t→r | Regular: r—a→u
ε-NFA E accepts string w iff:
δ̂(q0, w) ∩ F ≠ ∅
After processing w (with all ε-closures), at least one final state is an accept state.
The language recognized by E:
L(E) = { w ∈ Σ* | δ̂(q0, w) ∩ F ≠ ∅ }
Even if q0 is NOT an accept state, the ε-NFA might still accept ε! If any state in CL(q0) is an accept state, then ε ∈ L(E).
We can eliminate all ε-transitions to get an equivalent ordinary NFA.
Given ε-NFA E = (Q, Σ, δE, q0, F), build NFA N = (Q, Σ, δN, q0, F′):
| a | b | ε | |
|---|---|---|---|
| → q0 | ∅ | ∅ | {q1} |
| q1 | {q2} | ∅ | ∅ |
| q2 | ∅ | ∅ | {q3} |
| *q3 | ∅ | {q4} | ∅ |
| q4 | ∅ | ∅ | ∅ |
| a | b | |
|---|---|---|
| → q0 | {q2,q3} | ∅ |
| q1 | {q2,q3} | ∅ |
| *q2 | ∅ | {q4} |
| *q3 | ∅ | {q4} |
| q4 | ∅ | ∅ |
Student also marked F′ = {q2, q3}.
Click the buggy cell in the table above.
| a | b | ε | |
|---|---|---|---|
| → q0 | ∅ | ∅ | {q1, q4} |
| q1 | {q2} | ∅ | ∅ |
| q2 | ∅ | {q3} | ∅ |
| *q3 | ∅ | ∅ | ∅ |
| q4 | ∅ | {q5} | ∅ |
| *q5 | ∅ | ∅ | ∅ |
| a | b | |
|---|---|---|
| → q0 | -- | -- |
| q1 | -- | -- |
| q2 | -- | -- |
| *q3 | -- | -- |
| q4 | -- | -- |
| *q5 | -- | -- |
Skip the intermediate NFA — go straight from ε-NFA to DFA using modified subset construction.
It’s the algorithm you already know from NFA → DFA, except you wrap every intermediate result in CL(). Think: “subset construction wearing ε-closure glasses.”
| a | b | ε | |
|---|---|---|---|
| → q0 | ∅ | ∅ | {q1} |
| q1 | {q2} | ∅ | ∅ |
| q2 | ∅ | {q3} | ∅ |
| *q3 | ∅ | ∅ | ∅ |
| DFA State | ε-NFA States | a | b | Accept? |
|---|
Every regex operator maps to an ε-NFA pattern. This is how grep, lex, and regex engines work.
New start ⟶ ε to both sub-machines. Both final states ⟶ ε to new accept.
Final of R1 ⟶ ε to start of R2. Chain them together.
New start (also accept) ⟶ ε to R. Final of R ⟶ ε back to start. Handles zero repetitions.
ε-transitions let us compose automata like functions. Build small, test small, combine freely. This is the foundation of practical regex engines.
For each scenario, pick the best conversion approach.
“I have an ε-NFA and need a DFA for a hardware implementation.”
“I need to prove that (a|b)*a accepts the same strings as my DFA.”
“I want to combine three separate NFAs for L1, L2, L3 into one machine for L1∪L2∪L3.”
| Concept | Definition |
|---|---|
| ε-transition | Move without consuming input |
| CL(q) | All states reachable from q via ε* |
| CL(S) | ∪ CL(q) for all q in S |
| δ̂(q,ε) | = CL(q) |
| δ̂(q,xa) | = CL( δ( δ̂(q,x), a ) ) |
| Accepts w | δ̂(q0,w) ∩ F ≠ ∅ |
Converting an ε-NFA with n states to a DFA can produce at most how many states?
An ε-NFA has q0 ∉ F but CL(q0) ∩ F ≠ ∅. Does it accept ε?
If δ(q, ε) = ∅ for all states q, what is every CL(q)?
| a | b | ε | |
|---|---|---|---|
| → q0 | ∅ | ∅ | {q1} |
| q1 | {q2} | {q3} | ∅ |
| q2 | ∅ | ∅ | {q3} |
| *q3 | ∅ | ∅ | ∅ |
Fill in each step of δ̂(q0, “ab”):
ε: q0→{q1,q4} | a: q1→q2 | b: q2→q3, q4→q5 | F={q3,q5}