Suppose you already have one machine that recognises strings of a's and another that recognises strings of b's, and you want a machine for "some a's followed by some b's". It would be lovely to just draw an arrow from the end of the first machine to the start of the second, an arrow that you can take without reading anything.
That free arrow is called an ε-transition (epsilon-transition), and an NFA that is allowed to use such arrows is an ε-NFA. ε-moves make it very easy to glue machines together, which is why they are used everywhere: in converting regular expressions to automata, in lexer generators, and in textbook proofs about regular languages.
An ε-NFA is an NFA that may also have transitions labelled ε. Such a transition changes the state without consuming any input symbol.
In this chapter we will define ε-NFAs, learn to compute the ε-closure of a state (the key tool for everything else), run ε-NFAs on strings, and convert them to ordinary NFAs and to DFAs. As in the previous chapters, every machine and table here was checked by a program on all strings up to length 10 (length 30 for the one-letter example).
What an ε-Move Means
An arrow p –ε→ q says: "whenever you are in p, you may also be in q, for free". The input head does not move.
ε here is the empty string, not a symbol of the alphabet. The machine never "reads" an ε from the input.
Taking an ε-move is optional, like any nondeterministic choice. The machine may take it or stay.
ε-moves can be chained: p –ε→ q –ε→ r means r is reachable from p for free as well.
Think of ε-arrows as teleporters: standing on p, you are automatically also standing on every state you can teleport to.
Formal Definition
E = (Q, Σ, δ, q0, F)
δ : Q × (Σ ∪ {ε}) → 2^QThe only change from an NFA is that δ also accepts ε as a "label". We assume ε ∉ Σ.
ε-closure
ECLOSE(q), the ε-closure of q, is the set of all states reachable from q by following zero or more ε-transitions.
Formally, ECLOSE(q) is the smallest set such that:
q ∈ ECLOSE(q) (zero ε-moves, so a state is always in its own closure);
if p ∈ ECLOSE(q) and r ∈ δ(p, ε), then r ∈ ECLOSE(q).
For a set of states S, ECLOSE(S) = ⋃q ∈ S ECLOSE(q).
Algorithm
ε-closure is just graph reachability using only the ε-edges:
ECLOSE(S):
closure = S
stack = all states of S
while stack is not empty:
p = pop(stack)
for each r in δ(p, ε):
if r not in closure:
add r to closure
push r
return closureEach ε-edge is examined at most once, so this runs in time linear in the number of states and ε-edges.
Example 1: Computing ε-Closures (with an ε-cycle)
Σ = {0, 1}, start q0, final q4. A "–" means no transition.
State | 0 | 1 | ε |
|---|---|---|---|
→ q0 | {q0} | – | {q1} |
q1 | – | {q3} | {q2} |
q2 | {q4} | – | {q0} |
q3 | – | – | {q4} |
* q4 | – | {q4} | – |
ε-edges only:
q0 ──ε──► q1 ──ε──► q2 q3 ──ε──► q4
▲ │
└─────────ε──────────┘ (q0, q1, q2 form an ε-cycle)Computing ECLOSE(q0) with the stack algorithm:
closure = {q0} stack = [q0]
pop q0: δ(q0,ε) = {q1} → add q1 closure = {q0,q1} stack = [q1]
pop q1: δ(q1,ε) = {q2} → add q2 closure = {q0,q1,q2} stack = [q2]
pop q2: δ(q2,ε) = {q0} → already in closure stack = []
ECLOSE(q0) = {q0, q1, q2}Doing the same for every state:
State | ECLOSE |
|---|---|
q0 | {q0, q1, q2} |
q1 | {q0, q1, q2} |
q2 | {q0, q1, q2} |
q3 | {q3, q4} |
q4 | {q4} |
Because q0, q1, q2 lie on an ε-cycle, they all have the same closure. That is a general fact: states on a common ε-cycle are reachable from each other for free, so they are interchangeable.
The "visited" check is what stops the algorithm from looping forever around the cycle. Forgetting it is a classic bug.
Running an ε-NFA on a String
The set-of-states method from Nondeterministic Finite Automata (NFA) still works, with one change: take the ε-closure at the start and after every symbol.
δ̂(q, ε) = ECLOSE(q)
δ̂(q, wa) = ECLOSE( ⋃ δ(p, a) for p ∈ δ̂(q, w) )
L(E) = { w : δ̂(q0, w) ∩ F ≠ ∅ }So each step is: move on the symbol, then close under ε.
Trace of Example 1 on 0011:
start: ECLOSE(q0) = {q0,q1,q2}
read 0: move → δ(q0,0) ∪ δ(q2,0) = {q0,q4}; close = {q0,q1,q2,q4}
read 0: move → {q0,q4}; close = {q0,q1,q2,q4}
read 1: move → δ(q1,1) ∪ δ(q4,1) = {q3,q4}; close = {q3,q4}
read 1: move → δ(q4,1) = {q4}; close = {q4}
contains q4 → ACCEPTTrace on 010:
{q0,q1,q2} ─0─► {q0,q1,q2,q4} ─1─► {q3,q4} ─0─► ∅ REJECTTesting all strings shows that this machine accepts exactly the non-empty strings of the form 0m1n: some 0s followed by some 1s, at least one symbol in total. The empty string is rejected because ECLOSE(q0) = {q0, q1, q2} contains no final state.
Example 2: a*b*c*
Σ = {a, b, c}. We want any number of a's, then any number of b's, then any number of c's. This is the textbook use of ε: three one-state machines glued by ε-arrows.
──► q0 ──ε──► q1 ──ε──► ((q2))
⟲ a ⟲ b ⟲ cState | a | b | c | ε | ECLOSE |
|---|---|---|---|---|---|
→ q0 | {q0} | – | – | {q1} | {q0, q1, q2} |
q1 | – | {q1} | – | {q2} | {q1, q2} |
* q2 | – | – | {q2} | – | {q2} |
The ε-moves mean "I am done with this block, move on". Since the machine can move on at any time (including immediately), every block may be empty.
abbc: {q0,q1,q2} ─a─► {q0,q1,q2} ─b─► {q1,q2} ─b─► {q1,q2} ─c─► {q2} ACCEPT
aca : {q0,q1,q2} ─a─► {q0,q1,q2} ─c─► {q2} ─a─► ∅ REJECT
ba : {q0,q1,q2} ─b─► {q1,q2} ─a─► ∅ REJECT
ε : {q0,q1,q2} contains q2 ACCEPTConverting an ε-NFA to an NFA (Removing ε-Moves)
We can always remove the ε-arrows without changing the language and without adding states. For each state q and symbol a:
δ'(q, a) = ECLOSE( ⋃ δ(p, a) for p ∈ ECLOSE(q) )
F' = { q : ECLOSE(q) ∩ F ≠ ∅ }In words: from q, slide along ε-arrows, take one a-move, then slide along ε-arrows again. Every place you could end up becomes a direct a-arrow from q. And q becomes final if it can reach a final state using only ε-moves (otherwise we would lose strings, in particular ε itself).
Applying it to a*b*c*
δ'(q0, a) = ECLOSE(δ({q0,q1,q2}, a)) = ECLOSE({q0}) = {q0,q1,q2}
δ'(q0, b) = ECLOSE(δ({q0,q1,q2}, b)) = ECLOSE({q1}) = {q1,q2}
δ'(q0, c) = ECLOSE(δ({q0,q1,q2}, c)) = ECLOSE({q2}) = {q2}
δ'(q1, a) = ECLOSE(δ({q1,q2}, a)) = ∅
δ'(q1, b) = ECLOSE({q1}) = {q1,q2}
δ'(q1, c) = ECLOSE({q2}) = {q2}
δ'(q2, a) = ∅, δ'(q2, b) = ∅, δ'(q2, c) = {q2}State | a | b | c |
|---|---|---|---|
→* q0 | {q0, q1, q2} | {q1, q2} | {q2} |
* q1 | ∅ | {q1, q2} | {q2} |
* q2 | ∅ | ∅ | {q2} |
All three states are final, because each one's closure contains q2. Making q0 final is essential: the empty string has no arrow to follow, so the only way the new NFA can accept ε is for q0 itself to be final. The final-state rule is exactly what saves it.
Applying it to Example 1
State | 0 | 1 |
|---|---|---|
→ q0 | {q0, q1, q2, q4} | {q3, q4} |
q1 | {q0, q1, q2, q4} | {q3, q4} |
q2 | {q0, q1, q2, q4} | {q3, q4} |
* q3 | ∅ | {q4} |
* q4 | ∅ | {q4} |
Here q3 becomes final (its closure contains q4), but q0, q1, q2 do not, which is consistent with ε not being in the language.
Converting an ε-NFA Directly to a DFA
Subset construction from NFA to DFA Conversion (Subset Construction) works with two small changes:
start state S0 = ECLOSE(q0) (not just {q0})
transition δ_D(S, a) = ECLOSE( ⋃ δ(p, a) for p ∈ S ) (close after moving)
final states = subsets containing a state of Fa*b*c* to a DFA
S0 = ECLOSE(q0) = {q0,q1,q2}
a: ECLOSE({q0}) = {q0,q1,q2} = S0
b: ECLOSE({q1}) = {q1,q2} = S1 (new)
c: ECLOSE({q2}) = {q2} = S2 (new)
S1 = {q1,q2}
a: ∅ = S3 (new, dead)
b: ECLOSE({q1}) = {q1,q2} = S1
c: ECLOSE({q2}) = {q2} = S2
S2 = {q2}
a: ∅ = S3 b: ∅ = S3 c: {q2} = S2
S3 = ∅ → S3 on a, b, cDFA state | a | b | c |
|---|---|---|---|
→* S0 = {q0, q1, q2} | S0 | S1 | S2 |
* S1 = {q1, q2} | S3 | S1 | S2 |
* S2 = {q2} | S3 | S3 | S2 |
S3 = ∅ | S3 | S3 | S3 |
Four states, and this DFA is already minimal: S0, S1, S2 mean "still allowed to read a / b / c" respectively, and S3 is the trap.
Example 1 to a DFA
DFA state | 0 | 1 |
|---|---|---|
→ {q0, q1, q2} | {q0, q1, q2, q4} | {q3, q4} |
* {q0, q1, q2, q4} | {q0, q1, q2, q4} | {q3, q4} |
* {q3, q4} | ∅ | {q4} |
∅ | ∅ | ∅ |
* {q4} | ∅ | {q4} |
5 states. {q3, q4} and {q4} behave identically (both accept exactly 1*), so the minimal DFA has 4 states.
Example 3: Union with ε (Length Divisible by 2 or 3)
Σ = {a}, L = { an : n is divisible by 2 or by 3 }.
Build one small cycle for each condition, then add a new start state s with ε-arrows into both. The machine "guesses" which condition it is going to check.
┌──ε──► ((p0)) ──a──► p1 ──a──► (back to p0)
──► s ───┤
└──ε──► ((r0)) ──a──► r1 ──a──► r2 ──a──► (back to r0)ECLOSE(s) = {s, p0, r0}; every other state's closure is just itself. Subset construction:
DFA state | n mod 6 | a | Final? |
|---|---|---|---|
→ {s, p0, r0} | 0 (only for n = 0) | {p1, r1} | yes |
{p1, r1} | 1 | {p0, r2} | no |
{p0, r2} | 2 | {p1, r0} | yes |
{p1, r0} | 3 | {p0, r1} | yes |
{p0, r1} | 4 | {p1, r2} | yes |
{p1, r2} | 5 | {p0, r0} | no |
{p0, r0} | 0 | {p1, r1} | yes |
The DFA counts n mod 6 (the pair (n mod 2, n mod 3) determines it) and accepts residues 0, 2, 3, 4. It has 7 states because the start subset contains s; since {s, p0, r0} and {p0, r0} behave the same, the minimal DFA is a 6-cycle.
Why ε-Moves Are So Useful: Gluing Machines
Given machines M1 and M2 (each with one start and one final state), ε-arrows give simple constructions:
Operation | Construction with ε |
|---|---|
Union L1 ∪ L2 | New start state with ε-arrows to the start states of M1 and M2 |
Concatenation L1L2 | ε-arrow from the final state of M1 to the start of M2; only M2's final state stays final |
Kleene star L1* | New start/final arrangement with ε-arrows that allow skipping M1 entirely and looping back from its end to its start |
Optional part (x)? | An ε-arrow that bypasses the part |
For example, a signed integer such as -42 (sign optional, at least one digit d) is just: q0 –(+, −, or ε)→ q1 –d→ q2, with q2 looping on d and final. The ε-arrow makes the sign optional. These building blocks are developed fully, with exact rules, in Regular Expression to Finite Automata (Thompson's construction) and used to prove closure properties in Closure Properties of Regular Languages.
DFA vs NFA vs ε-NFA
Feature | DFA | NFA | ε-NFA |
|---|---|---|---|
δ type | Q × Σ → Q | Q × Σ → 2Q | Q × (Σ ∪ {ε}) → 2Q |
Moves without input | No | No | Yes |
Start of simulation | q0 | {q0} | ECLOSE(q0) |
Ease of combining machines | Hard (product constructions) | Moderate | Very easy |
Languages accepted | Exactly the regular languages (all three are equivalent) | ||
ε-NFA → NFA keeps the same states (ε-elimination); ε-NFA → DFA uses subset construction with ε-closures. So ε-moves add convenience, not power.
Common Mistakes
Leaving the state itself out of its closure. q ∈ ECLOSE(q) always, even when q has no ε-arrows.
Closing only once. You must take the ε-closure at the start and after every symbol move.
Using only direct ε-arrows. Closure follows chains: p –ε→ q –ε→ r puts r in ECLOSE(p).
Forgetting the final-state rule when removing ε-moves: a state is final in the new NFA if its closure contains an old final state. Otherwise ε (and sometimes other strings) can be lost.
Starting the DFA from {q0} instead of ECLOSE(q0).
Thinking ε is read from the tape. ε-moves consume nothing; the input head does not move.
Looping forever on ε-cycles in hand or program computation. Keep a visited set.
Practice and GATE-Style Questions
Q1. States 1–4 with ε-arrows 1 → 2, 2 → 3, 3 → 1 and 2 → 4 (no others). Find the ε-closure of each state.
1, 2, 3 are on an ε-cycle, and 2 reaches 4. So ECLOSE(1) = ECLOSE(2) = ECLOSE(3) = {1, 2, 3, 4} and ECLOSE(4) = {4}.
Q2. In an ε-NFA, the start state is not final but there is an ε-path from it to a final state. Is ε in the language?
Yes. δ̂(q0, ε) = ECLOSE(q0), which contains the final state. In the ε-free NFA built by ε-elimination, q0 becomes a final state for exactly this reason.
Q3. For the a*b*c* ε-NFA in this chapter, compute δ̂(q0, ab) and δ̂(q0, ca).
δ̂(q0, ab): {q0, q1, q2} –a→ {q0, q1, q2} –b→ {q1, q2} (accepted). δ̂(q0, ca): {q0, q1, q2} –c→ {q2} –a→ ∅ (rejected).
Q4. Does removing ε-transitions (ε-NFA → NFA) ever need more states?
No. The standard ε-elimination keeps exactly the same state set; only the arrows and the set of final states change. (It may add many arrows.) Converting to a DFA is what can increase the number of states, up to 2n.
Q5. An ε-NFA for a*b*c* has 3 states. How many states does the DFA from subset construction have?
4: {q0, q1, q2}, {q1, q2}, {q2} and the dead state ∅.
Q6. Interview: why do tools build ε-NFAs at all if they are eventually turned into DFAs?
Because building an automaton from a regular expression is very simple with ε-arrows: each operator (union, concatenation, star) becomes a small fixed pattern of ε-arrows. The tool then removes ε by subset construction with ε-closures (and usually minimises). It is a clean pipeline: regex → ε-NFA → DFA → minimal DFA.
Summary
An ε-NFA allows transitions on ε, which change state without reading input.
ECLOSE(q): all states reachable from q using zero or more ε-moves; always contains q.
Simulation: start with ECLOSE(q0); for each symbol, move then close.
ε-NFA → NFA: δ'(q, a) = ECLOSE(δ(ECLOSE(q), a)); q is final if ECLOSE(q) contains a final state. Same number of states.
ε-NFA → DFA: subset construction starting from ECLOSE(q0) and closing after every move.
ε-arrows make union, concatenation, star and "optional" parts trivial to build.
DFA, NFA and ε-NFA all accept exactly the regular languages.
Whenever you land somewhere in an ε-NFA, you are also everywhere the ε-arrows can take you. Close, move, close again.