Theory of Automata

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”.

Epsilon NFA (∈-NFA) example 1

Example 02

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

Epsilon NFA (∈-NFA) example 2



Example 03

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

Epsilon NFA (∈-NFA) example 3

Example 04

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

Epsilon NFA (∈-NFA) example 4

Example 05

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

Epsilon NFA (∈-NFA) example 5

 

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest