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, ∑, δ, q0, F) where,
- Q is a finite set of all states (q0, q1, q2, … qn) where n is finite number
- ∑ is a finite set of symbols called the alphabet. i.e. {0, 1},
- δ : Q x (∑ U ∈) → 2Q is a total function called as transition function
- q0 is the initial state from where any input is processed (q0 ∈ 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