Epsilon-NFA and its conversion
How epsilon-NFAs (ε-NFAs) work and how to convert them to equivalent NFAs and DFAs using ε-closure and subset construction.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Finite automata are a basic model of computation used in lexical analysis, pattern matching, network protocol verification, and hardware control. The ε-NFA (epsilon-NFA) is a nondeterministic finite automaton that allows spontaneous moves (epsilon transitions). Understanding ε-NFAs and how to convert them to NFAs and DFAs is essential for turning specifications (regular expressions, grammars) into implementable deterministic machines used in compilers and embedded systems.
Key ideas
- Start state (q0): The state where the machine begins. (Defined before use.)
- Accepting / final states (F): Subset of Q whose membership determines acceptance.
- Transition function (δ): For an ε-NFA, δ: Q × (Σ ∪ {ε}) → P(Q); for an NFA (without ε), δ: Q × Σ → P(Q). (Defines moves.)
- ε-NFA: A 5-tuple M = (Q, Σ, δ, q0, F) where δ may include transitions labelled with ε (empty string). An ε transition means the machine can move from one state to another without reading any input symbol.
Exact formal definition of ε-NFA language acceptance:
- Let δ be the transition function that may return a set of next states for a state and a symbol in Σ ∪ {ε}.
- Define ε-closure of a state q, written
ε-closure(q), to be the set of states reachable from q by zero or more ε-transitions. For a set S ⊆ Q,ε-closure(S) = ⋃_{q∈S} ε-closure(q). - Define the extended transition δ*(S, w) on strings formally: for S ⊆ Q, δ*(S, ε) = ε-closure(S); for w ∈ Σ*, a ∈ Σ, δ*(S, wa) = ε-closure(⋃_{p ∈ δ*(S, w)} δ(p, a)).
- A string w ∈ Σ* is accepted by the ε-NFA iff δ*({q0}, w) ∩ F ≠ ∅.
Key theorem (exact statement often required in exams):
- Every ε-NFA has an equivalent NFA (without ε transitions) and thus an equivalent DFA. That is, for every ε-NFA M there exists an NFA M' such that L(M) = L(M'). Proof is constructive by computing ε-closures and redefining transitions.
Algorithm (to remove ε-transitions and form equivalent NFA):
- For each state q compute
ε-closure(q). - Define new transition function δ' for every q ∈ Q and symbol a ∈ Σ by: δ'(q, a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p, a)).
- Define new set of final states F' = { q ∈ Q | ε-closure(q) ∩ F ≠ ∅ }.
- The resulting NFA is (Q, Σ, δ', q0, F').
Why step 2 and 3 work: Step 2 ensures any a-move that could be taken after zero or more ε-moves is captured. Taking ε-closure of the result preserves further ε-moves after the a-move. Step 3 ensures states that could reach an accepting state by ε alone are accepting in the new automaton.
Alternative direct conversion to DFA (subset construction with ε-closures):
- Compute start state of DFA as
S0 = ε-closure({q0}). - For each DFA state S (a set of NFA states) and input a ∈ Σ compute
move(S, a) = ⋃_{p ∈ S} δ(p, a), thenδ_DFA(S, a) = ε-closure(move(S, a)). - Any DFA state S that contains a member of F is accepting.
- Repeat until no new DFA states appear. The constructed DFA has at most 2^|Q| states.
Assumptions behind correctness: finite Q, Σ, and transition relation well-defined; ε is distinct from symbols in Σ; closure and union operations are standard set operations. The construction preserves language because it simulates all possible ε-moves at the moment they can occur.
Diagram instructions (for exam answers requiring a picture): draw circles labeled q0, q1, etc. Mark q0 with an incoming arrow (start). Mark final states with double circle. Draw arrows labelled with input symbol or with the Greek letter ε for epsilon transitions. Example to draw: q0 --ε--> q1, q1 --a--> q1, q1 --b--> q2 (double circle). Label everything clearly.
Formulas
ε-closure(q) = { p ∈ Q | p is reachable from q by 0 or more ε-transitions } — q: state in Q; unit: dimensionless; applies when computing reachable states via ε.
ε-closure(S) = ⋃_{q ∈ S} ε-closure(q) — S: subset of Q.
δ'(q, a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p, a)) — δ': transition function of resulting NFA; a ∈ Σ; δ(p,a) returns set of states; unit: dimensionless; applies when removing ε-transitions.
F' = { q ∈ Q | ε-closure(q) ∩ F ≠ ∅ } — F': new final states.
S0 = ε-closure({q0}) — start state for DFA conversion; S0 is a subset of Q.
move(S, a) = ⋃_{p ∈ S} δ(p, a) — intermediate set when constructing DFA.
δ_DFA(S, a) = ε-closure(move(S, a)) — DFA transition function.
(Units: these are abstract sets and functions — dimensionless.)
Worked examples
Example 1 — Remove ε-transitions (small exam-style question). Given ε-NFA with Q = {q0,q1,q2}, Σ = {a,b}, q0 start, F = {q2}. Transitions:
- δ(q0, ε) = {q1}
- δ(q1, a) = {q1}
- δ(q1, b) = {q2}
- No other transitions (implicit empty set).
Step 1: compute ε-closures:
- ε-closure(q0) = {q0} ∪ states reachable by ε from q0 = {q0, q1}.
- ε-closure(q1) = {q1} (no ε out of q1).
- ε-closure(q2) = {q2}.
Step 2: compute δ' for a and b using formula δ'(q,a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p,a)).
- δ'(q0, a) = union over p in {q0,q1} of ε-closure(δ(p,a)). δ(q0,a) = ∅, δ(q1,a) = {q1}. So δ'(q0,a) = ε-closure({q1}) = {q1}.
- δ'(q0, b) = union over {q0,q1} of ε-closure(δ(p,b)). δ(q0,b)=∅, δ(q1,b)={q2}. So δ'(q0,b) = ε-closure({q2}) = {q2}.
- δ'(q1, a) = ε-closure(δ(q1,a)) = ε-closure({q1}) = {q1}.
- δ'(q1, b) = ε-closure({q2}) = {q2}.
- δ'(q2, a) = ∅, δ'(q2, b) = ∅.
Step 3: final states F' = { q | ε-closure(q) ∩ {q2} ≠ ∅ } = { q2 } (only q2's closure contains q2). Note: q0's closure {q0,q1} does not contain q2.
Result: NFA without ε with the same states, transitions δ' listed above, start q0, final {q2}.
Example 2 — Convert same ε-NFA directly to DFA (subset construction). Step A: S0 = ε-closure({q0}) = {q0,q1}. Compute transitions from {q0,q1}:
- move({q0,q1}, a) = δ(q0,a) ∪ δ(q1,a) = ∅ ∪ {q1} = {q1}; δ_DFA({q0,q1}, a) = ε-closure({q1}) = {q1}.
- move({q0,q1}, b) = ∅ ∪ {q2} = {q2}; δ_DFA({q0,q1}, b) = ε-closure({q2}) = {q2}.
New DFA states discovered: {q1}, {q2}. Compute for {q1}:
- move({q1}, a) = {q1} → δ_DFA({q1}, a) = {q1}.
- move({q1}, b) = {q2} → δ_DFA({q1}, b) = {q2}.
Compute for {q2}:
- move({q2}, a) = ∅ → δ_DFA({q2}, a) = ε-closure(∅) = ∅ (dead set). Similarly for b.
Include dead state ∅ with self-loops to remain complete if needed.
Accepting DFA states: any set containing q2, so {q2} and any other set with q2 (none else here) are accepting.
Final DFA states: S0 = {q0,q1} (non-accepting), {q1} (non-accepting), {q2} (accepting), and ∅ (non-accepting dead state). Transitions as computed.
This example shows how DFA can be built step-by-step; exam answers should list each computed set and transition.
Common mistakes
- Using ε as if it were a real symbol in Σ (ε is not part of Σ).
- Not adding the dead (empty) set as a DFA state when completeness is required by the question.
- In subset construction, forgetting to stop when no new subsets arise (incomplete state exploration).
For your exam
Types of questions:
- Definition and short notes: define ε-NFA, ε-closure, compare ε-NFA and NFA, state the theorem that every ε-NFA is equivalent to an NFA/DFA.
- Derivation/proof: prove correctness of the ε-removal construction (show language-preserving), or derive δ' formula step-by-step.
- Algorithm trace: given a small ε-NFA, compute ε-closures, show δ' and F', or convert to DFA with subset construction; draw transition diagram.
- Diagram question: draw a given ε-NFA and its equivalent DFA.
What a full-marks answer includes:
- Clear definitions of terms used (ε, ε-closure, δ, Q, Σ, q0, F).
- Correct computation of ε-closures with justification.
- Correct application of the formula
δ'(q, a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p, a))and correct listing of new final statesF'. - For DFA construction, explicit listing of each DFA state (subset), transitions, and marking of accepting states. If asked, draw the state diagram and label start/accepting states and transitions.
Quick check
- What is
ε-closure(q)? - Give the formula for δ' when removing ε-transitions.
- How do you choose DFA start state when converting from an ε-NFA?
Answers: 1) The set of states reachable from q by zero or more ε-transitions. 2) δ'(q, a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p, a)). 3) S0 = ε-closure({q0}).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?