Epsilon NFA  (∈-NFA)

Epsilon NFA (∈-NFA) is similar to the NFA but with a little difference in that it has an epsilon (∈) transition that NFA doesn’t have. A Transition that does not consume any input symbol is called an ε-transitions.

• ∈-NFA state diagrams usually label Epsilon with the Greek letter “∈”. It is also called lambda.
• ∈-transitions give a convenient way of designing the machine systems.
• Due to ε-transitions, the first string of language may be empty.

Note: ∈ab∈a = aba, where ∈ is empty. Epsilon (∈) transition is also known as an empty move or empty transition.

Formal Definition of Epsilon-NFA

The formal definition of  ∈-NFA is represented through 5-tuple (Q, ∑, δ, q₀, F) where,

• Q is a finite set of all states (q_0, q_1, q_{2,   …,} q_n) where n is a finite number.
• ∑ Is a finite set of symbols called the alphabet. i.e. {0, 1}.
• δ : Q x (∑ U ∈) → 2^Q is a total function called as transition function.
• q₀ is the initial state from where any input is processed (q₀ ∈ Q).
• F is a set of final states where F will be a subset ( ⊆ ) of Q.

Examples of Epsilon-NFA

There are various examples of epsilon-NFA. Let’s explain some of them.

∈ – NFA: Example 01

Draw a Finite Automata which accepts the string “ab”.

∈ – NFA: Example 02

Draw a Finite Automata which accepts the string “a or b”.

∈ – NFA: Example 03

Draw a Finite Automata that accepts the string “a, b or c”.

Epsilon-NFA: Example 04

Draw a Finite Automata that accepts the string “a*”.

∈ – NFA: Example 05

Create a ∈-NFA for regular expression: (b)*a

 

Elimination of Epsilon (ε) From NFA

If the epsilon exists between any two states in automata, then the removal of epsilon through some rules is called elimination of epsilon move from NFA.

Suppose there are two vertices, V1 and V2; the epsilon between them is below.

Steps For Elimination Of Epsilon From NFA

• Step 01: Find all edges starting from V2
• Step 02: Remove the epsilon. All Finding edges from V2 are Duplicated to V1 without changing edge labels.
• Step 03: if V1 is initial state, make V2 initial
• Step 04: if V2 is final state, make V1 final
• Step 05: Remove all dead states

Note: if more than one epsilon exists in epsilon-NFA, then first remove the epsilon that is far away from the initial state. After the Removal of one epsilon, remove the others till the removal of the epsilon is.

Example of Elimination Of Epsilon From NFA

Let’s discuss various examples according to given steps for elimination of epsilon from NFA

Example 01:

Consider the following epsilon NFA

Solution

In the above epsilon NFA, suppose q0 is a V1 and q2 is V2 because epsilon exists between these two states. Now apply the steps of epsilon removal.

Step 01

• The first input, “0”, starts from V2 (q2) and goes to q3.
• The second input, “1”, starts from V2 (q2) and goes to q4

Step 02

Finding outgoing edges from V2 are “0” and “1”.

• First, Input “0” is going to q3 from V2 (q2). So, the first duplicate will go from V1 (q0) to q3.
• Second Input “1” is going to q4 from V2 (q2). So, the second duplicate will go from V1 (q0) to q4.

So, duplicated edges with their labels are given below

Step 03

As V1 (q0) is an initial. So V2(q2) changes to initial. As given below

Step 04

As V2 (q2) is a final state. So V1(q0) changes to the final state. As given below

Step 05

An unreachable state is called a dead state. In the above NFA, there is no dead state. So, the final NFA after the removal of epsilon is given below.

 

Example02:

Consider the following epsilon NFA

Solution

In the above epsilon NFA,  there are two epsilon exist. First, we remove the epsilon, away from the initial state. So, first, we remove the epsilon which exists in q1 and q4.

Suppose q1 is V1 and q4 is V2 because epsilon exists between these two states. Now apply the steps of epsilon removal.

Step 01: 

• The only input “0” begins from V2 (q4) and goes to q5.

Step 02: 

As the Input “0” is going to q5 from V2 (q2). So, a duplicate will go from V1 (q1) to q5. So, duplicated edges with their labels are given below.

Step 03: 

As V1 (q1) is not an initial state. So V2(q2) will be unchanged, and the NFA  of Step 2 remain the Same.

Step 04:

As V2 (q4) is not a final state. So, V1(q1) will be unchanged, and the NFA  of Step 2 remain the Same.

Step 05:

An unreachable state is called a dead state. In the above NFA, q4 is the dead state. So, NFA after removal of the first epsilon and dead state is given below.

Now Repeat the Above 5 steps again for elimination of 2nd epsilon.

After the first 5 steps, epsilon- NFA, epsilon exists between q0 and q1. Again, suppose q0 is V1 and q2 is V2.

Again Step 01: Find all edges starting from V2

• The only input “0” begins from V2 (q2) and goes to q3.

Step 02: Remove the epsilon. All Finding edges from V2 are Duplicated to V1 without changing edge labels.

As the Input “0” is going to q3 from V2 (q1). So, a duplicate will go from V1 (q0) to q3. So, duplicated edges with their labels are given below.

Step 03:

As V1 (q0) is an initial state. So V2(q1) will be changed to final. As given below

Step 04:

As V2 (q1) is not a final state. So, V1(q1) will remain unchanged, and the NFA of the above step3 will remain the same.

Step 05: Remove all dead states

No dead state was found. The above NFA of step 3 will remain the same. So, the final NFA after eliminating both epsilons and dead states is given below.