Eliminating Epsilon Transitions from NFA

 Eliminating ε (epsilon or empty string) transitions from an NFA (Non-deterministic Finite Automaton) involves converting an ε-NFA to an equivalent NFA without ε-transitions.

🔁 Goal:

Given an ε-NFA, produce an NFA (no ε-transitions) that accepts the same language.

---

🧠 Key Concept: ε-Closure

The ε-closure of a state q, written as ε-closure(q), is the set of states reachable from q by zero or more ε-transitions.

For a set of states S,

ε-closure(S) = union of ε-closure(s) for all s ∈ S

---

📘 Formal Algorithm to Eliminate ε-Transitions:

Input:

An ε-NFA E = (Q, Σ, δ, q₀, F)

Output:

An equivalent NFA N = (Q, Σ, δ', q₀', F') without ε-transitions

---

🧩 Step-by-step Algorithm:

1. Compute ε-closure for each state q ∈ Q

   • ε-closure(q) includes q itself and all states reachable from q using only ε-transitions.

2. Redefine transition function δ':
   For each state q ∈ Q and symbol a ∈ Σ:

   • Let T = ∅

   • For each state p ∈ ε-closure(q):

     • For each state r ∈ δ(p, a):

       • Add ε-closure(r) to T

   • Define δ'(q, a) = T

3. Define new final states F':

   • A state q ∈ Q is in F' if any state in ε-closure(q) is in F

4. Initial state remains the same: q₀' = q₀

---

✅ Result:

The new automaton N = (Q, Σ, δ', q₀, F') has no ε-transitions, and it accepts the same language as the original ε-NFA.

Epsilon-NFA to NFA Conversion Steps in Detail

Step 1: Find the Epsilon Closure

• For each state in the Epsilon-NFA, find its epsilon closure.
• This means figuring out all the states that can be reached by only using epsilon transitions (and include the state itself).
• This helps in tracking which states can be reached without reading any input symbol.

Step 2: Create New States for the NFA

• Each state in the new NFA corresponds to a set of states you found in the epsilon closures.
• The starting state in the NFA will be the epsilon closure of the initial state of the Epsilon-NFA.

Step 3: Define the Transitions

• For each state in the NFA (which represents a group of states from the epsilon closures), look at what happens when you read each input symbol.
• For an input symbol a, check which states you can reach from any state in the current group, and then find the epsilon closure of those states.
• This way, you're considering both direct transitions and the ones that happen because of epsilon moves.

Step 4: Set Accepting States

• Any state in the NFA that includes at least one accepting state from the Epsilon-NFA becomes an accepting state.
• This ensures that the NFA recognizes all the same strings as the Epsilon-NFA.

Step 5: Keep Going Until Done

• Keep processing each new state and its transitions until no more new states are created.
• This guarantees that every possible state is covered, and there are no epsilon transitions left.

Example of Epsilon-NFA to NFA Conversion

Convert the following ε-NFA to NFA. The ε-NFA has states q0, q1, q2, q3, q4 where q0 is the initial state and q2 final state.

Note: epsilon closure of q0 contain q2 so q0 is also final state.

Convert the following epsilon-NFA into Epsilon free NFA

epsilon free NFA is given below. Note that the epsilon closure of q0 , q1 and q2 contains q2 so all states are final states.