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

Updated 30 Oct 20266 min read136 views
Epsilon NFA Conversion: Epsilon-Closure, Worked DFA Table and Exam Traps

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 q0

  • F = {q3}

  • transitions: q0 -epsilon-> q1, q1 -epsilon-> q2, q1 -0-> q1, and q2 -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:

  1. S0 = E({q0}) = {q0,q1,q2}.

  2. First 0: move(S0,0) = {q1}, so E({q1}) = {q1,q2}.

  3. Second 0: move({q1,q2},0) = {q1}, so the closure remains {q1,q2}.

  4. Final 1: move({q1,q2},1) = {q3}, and E({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.

Epsilon-NFA with q0 to q1 to q2 to accepting q3, closures listed at right, and accepted 001 and rejected 010 traces below.

Convert the epsilon-NFA directly to a DFA

The direct algorithm is:

  1. Make E({q0}) the DFA start state.

  2. For each unprocessed subset T and each a in Sigma, compute U = E(move(T,a)).

  3. Add U if it is new, then continue until no reachable subset remains.

  4. 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

A = {q0,q1,q2}

B

C

B = {q1,q2}

B

C

C = {q3}

D

D

D = empty set

D

D

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.

Four-state DFA with subset states A, B, C, and dead state D, its complete 0/1 transition table, and 001 and 010 traces.

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

q0

{q1,q2}

{q3}

q1

{q1,q2}

{q3}

q2

empty set

{q3}

q3

empty set

empty set

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. Here move(A,0) = {q1}, but the next state is E({q1}) = {q1,q2}, not {q1}.

  • Using the wrong final-state test: a DFA subset is final when its intersection with F is 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^n states: 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.