Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

  1. For each state q compute ε-closure(q).
  2. Define new transition function δ' for every q ∈ Q and symbol a ∈ Σ by: δ'(q, a) = ⋃_{p ∈ ε-closure(q)} ε-closure(δ(p, a)).
  3. Define new set of final states F' = { q ∈ Q | ε-closure(q) ∩ F ≠ ∅ }.
  4. 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):

  1. Compute start state of DFA as S0 = ε-closure({q0}).
  2. 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)).
  3. Any DFA state S that contains a member of F is accepting.
  4. 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 states F'.
  • 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

  1. What is ε-closure(q)?
  2. Give the formula for δ' when removing ε-transitions.
  3. 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?