Epsilon NFA  (∈-NFA)

Epsilon NFA (∈-NFA) is similar to the NFA but have just a minor difference which is epsilon (∈) move. The transitions without consuming an input symbol are called ∈-transitions.

• In the state diagrams, they are usually labeled with the Greek letter ∈ also called lamda.
• ∈-transitions provide a convenient way of modeling the systems
• Due to empty move, the first string of language may be a empty or epsilon.

Note: ∈ab∈a = aba, where ∈ is empty.

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 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 state/states where F will be subset ( ⊆ ) of Q.

Examples of Epsilon-NFA

There are various examples of epsilon-NFA. let explain some of them.

Example 01

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

Example 02

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

Example 03

Draw a Finite Automata which can accept the string “a or b or c”.

Example 04

Draw a Finite Automata which accept the string “a*”

Example 05

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