Epsilon NFA Conversion: Epsilon-Closure, Worked DFA Table and Exam Traps
Learn a mechanical epsilon-NFA conversion method through one four-state machine, complete set traces, a reachable-subset DFA table, and epsilon elimination.
KnowledgeGate Team
Exam prep & CS education

An epsilon edge changes the active state set without consuming input. That small rule makes an apparently ordinary subset conversion easy to get wrong, because a missed path can silently change the language. The reliable routine is mechanical: compute epsilon-closures, apply move, generate reachable subsets, and check the result on strings. The focus is epsilon-NFA tracing, direct conversion, and epsilon elimination; A separate treatment covers the wider DFA/NFA comparison.
Related reading: epsilon NFA conversion MCQs test the same closure rules. The earlier NFA to DFA conversion for GATE: subset construction and state-count numericals owns ordinary subset construction and state-count numericals; this post focuses on epsilon-closure tracing and epsilon elimination.
What an epsilon-NFA adds to an ordinary NFA
An epsilon-NFA is M = (Q, Sigma, delta, q0, F), where
delta: Q x (Sigma union {epsilon}) -> 2^Q.
An epsilon transition changes state while consuming zero input symbols. Epsilon is a machine move, not a character in the input alphabet, so a DFA transition table never gets an epsilon input column.
The epsilon-closure of a state q, written E(q), contains every state reachable from q using zero or more epsilon moves. It includes q itself. For a set T, take the union of individual closures:
E(T) = union of E(q) for every q in T.
Closure is transitive. If q0 -epsilon-> q1 -epsilon-> q2, then E(q0) contains q0, q1, and q2.
To process a string, start at E({q0}). For each real symbol a, calculate E(move(currentSet, a)). After all input is consumed, accept exactly when the final set intersects F.
Compute epsilon-closures before touching the DFA table
Consider this machine:
Q = {q0,q1,q2,q3}Sigma = {0,1}start state
q0F = {q3}transitions:
q0 -epsilon-> q1,q1 -epsilon-> q2,q1 -0-> q1, andq2 -1-> q3
Every unlisted transition is the empty set. Its closures are:
E(q0) = {q0,q1,q2}E(q1) = {q1,q2}E(q2) = {q2}E(q3) = {q3}
For E(q0), include q0 by the zero-move rule, reach q1 on the first epsilon edge, then reach q2 on the second. Stop there because q2 has no epsilon exit.
The machine can follow the epsilon chain to q2 immediately and read 1. Alternatively, it can read any number of 0s using the loop at q1, take epsilon to q2, and read one final 1. Its language is exactly 0*1. Thus 1, 01, and 001 are accepted, while epsilon, 0, 10, and 0011 are rejected.
Trace strings by alternating move and epsilon-closure
Trace 001 in sets:
S0 = E({q0}) = {q0,q1,q2}.First
0:move(S0,0) = {q1}, soE({q1}) = {q1,q2}.Second
0:move({q1,q2},0) = {q1}, so the closure remains{q1,q2}.Final
1:move({q1,q2},1) = {q3}, andE({q3}) = {q3}.
The final set contains q3, so 001 is accepted. In contrast, 010 follows {q0,q1,q2} -0-> {q1,q2} -1-> {q3} -0-> empty set and is rejected. For the empty string, the final set is the start closure {q0,q1,q2}. It does not contain q3, so epsilon is rejected.
One successful path is enough for NFA acceptance, but set tracing retains every possible path. Never stop merely because an accepting state appears while unread input remains.

Convert the epsilon-NFA directly to a DFA
The direct algorithm is:
Make
E({q0})the DFA start state.For each unprocessed subset
Tand eachainSigma, computeU = E(move(T,a)).Add
Uif it is new, then continue until no reachable subset remains.Mark a subset accepting if it contains at least one state from
F.
Only reachable subsets are generated. Here they are A = {q0,q1,q2}, the start state; B = {q1,q2}; C = {q3}, the only accepting state; and D = empty set, the dead state.
DFA state | On 0 | On 1 |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
For one complete cell calculation:
delta_DFA(A,0) = E(move({q0,q1,q2},0)) = E({q1}) = {q1,q2} = B.
Now 001 follows A -0-> B -0-> B -1-> C and accepts. Input 010 follows A -0-> B -1-> C -0-> D and rejects. This agrees with the epsilon-NFA traces.
Subset construction and minimisation are separate stages. A and B have the same accepting status and transitions, so a later minimisation pass may merge them, but the unminimised conversion table must show both reachable subsets. In ordinary NFA-to-DFA conversion, there is no epsilon closure. Here, closure is required before the first input and after every move.

Alternative route: eliminate epsilon transitions first
For each state q and real symbol a, define:
delta'(q,a) = E(move(E(q),a)).
The new accepting set is F' = {q in Q | E(q) intersects F}. This second rule matters whenever a non-final state reaches a final state using epsilon alone.
Applying both rules gives the complete epsilon-free NFA:
State | On 0 | On 1 |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
The accepting set remains {q3} because the closure of no other state contains q3. No epsilon edge remains.
As a separate check, suppose p -epsilon-> f and f is final. Then E(p) = {p,f}, so p must enter F'. Otherwise the epsilon-free machine would incorrectly reject the empty string. Direct conversion folds closure into subset construction; elimination first creates an ordinary NFA that can then be determinised. Both preserve the language.
Conversion traps and the exact repair for each
Omitting the source or stopping closure early:
E(q0)is not{q1,q2}or{q0,q1}. Closure includes the source and follows epsilon edges to a fixed point, producing{q0,q1,q2}.Treating epsilon as input: keep
Sigma = {0,1}. Do not add an epsilon column to the DFA.Applying closure only at the start: use
E(move(T,a))after every symbol. Heremove(A,0) = {q1}, but the next state isE({q1}) = {q1,q2}, not{q1}.Using the wrong final-state test: a DFA subset is final when its intersection with
Fis non-empty, not only when every member is final.Deleting the empty subset: if it is reachable, include it and give it total self-loops.
Assuming exactly
2^nstates: this is an upper bound. Generate reachable subsets only.Minimising during conversion: complete the reachable-subset table first. Minimise only as a later operation.
How objective questions test epsilon-NFA conversion
Typical questions ask for one closure, the active set after a prefix, the correct DFA start or accepting subset, the count of reachable states, or an error in an epsilon-elimination table. In this example, the start subset is A = {q0,q1,q2}, the state after 00 is B = {q1,q2}, and the state after 001 is accepting state C = {q3}.
Use this answer routine: write every single-state closure, circle E({q0}), compute move before closure for every symbol, name each new reachable subset, mark every subset intersecting F, and add the empty-set row if reached. Audit the table with one accepted trace and one rejected trace.
KnowledgeGate has more than 10 practice questions in the Epsilon NFA & Conversion subtopic. That count describes practice availability, not official weightage or how often an examination asks the topic.
Short version and the next practice step
Remember four rules: epsilon consumes nothing; closure includes the state itself and every epsilon-reachable state; the DFA starts at E({q0}); and every DFA transition is E(move(T,a)). The worked machine recognises 0*1: 001 reaches {q3}, while 010 reaches the empty set.
As a self-test, rebuild the four-row DFA table without looking. Then trace 1, 0001, epsilon, 00, and 11. The outcomes should be accept, accept, reject, reject, and reject. Explain each answer from its final subset.
For a structured path through this material, continue with Theory Of Computation / Automata Theory. Once you can reproduce the table cleanly, use the GATE CS and IT Guidance by Sanchit Sir for follow-on practice. The CS Fundamentals for Exams & Placements collection connects automata with the wider subject set.
Keep learning
Non-Deterministic Finite Automata (NFA): Design, Epsilon Closures and NFA-to-DFA Conversion
Learn to follow every branch of an NFA without guesswork. Two worked machines connect active-state sets, epsilon closure and a complete eight-state DFA conversion.
Epsilon NFA Conversion MCQs: 10 Solved Questions with Explanations
Solve ten epsilon NFA MCQs step by step, from closure traces and shortest accepted strings to subset construction and NFA-DFA equivalence.
NFA to DFA Conversion: Subset Construction, Worked Example, and Exam Traps
Learn subset construction by converting one three-state NFA row by row, checking the result with strings, and then minimising the reachable DFA.
NFA to DFA Conversion for GATE: Subset Construction and State-Count Numericals
Convert two small NFAs into complete DFAs, handle epsilon-closure and the dead state, and separate the reachable state count from the 2^n worst case.





