Epsilon Closure of NFA

 

ε-Closure (Epsilon-Closure) of an NFA 

In a Non-deterministic Finite Automaton (NFA) with ε-transitions (also called λ-transitions), the ε-closure (or epsilon-closure) of a state refers to:

The set of states that can be reached from a given state (or set of states) using only ε-transitions (without consuming any input symbol).

---

🔍 Why is ε-closure important?

• When converting an NFA with ε-moves to a DFA, we need to compute ε-closures to determine the actual set of reachable states.

• ε-transitions represent free moves; we can jump from one state to another without reading input.

• Knowing ε-closure helps in simplifying and analyzing automata.

---

✅ Formal Definition

Let ε-closure(q) be the ε-closure of a state q. Then,

• q ∈ ε-closure(q) (because we can always reach the state itself without moving).

• If there's a transition q ⟶ε p, then p ∈ ε-closure(q).

• If p ∈ ε-closure(q) and p ⟶ε r, then r ∈ ε-closure(q). (This is transitive closure.)

We keep expanding until no new states are added.

---

🧠 Example

Let’s say we have the following ε-transitions in an NFA:

• q0 ⟶ε q1

• q1 ⟶ε q2

• q2 ⟶ a → q3

Now compute:

ε-closure(q0):

• Start with {q0}

• From q0, ε ⟶ q1, so add q1

• From q1, ε ⟶ q2, so add q2

• No ε-transition from q2

👉 So, ε-closure(q0) = {q0, q1, q2}

---

🧮 Example in Table Form

State	ε-transitions	ε-closure
q0	q1	{q0, q1, q2}
q1	q2	{q1, q2}
q2	-	{q2}

🧾 In Conversion to DFA:

When building DFA from an NFA with ε-moves:

1. Start with ε-closure of the NFA’s start state.

2. Treat each ε-closure set as a single DFA state.

3. Compute transitions for each symbol from all members of the closure.

Example: Find the ε-closure

• E closure( A) : {A, B,C}
• E closure( B) :{B,C}
• E closure( C) : {C}

Find epsilon closure of all states of the following NFA