What is the formal definition of epsilon or ε-closure?

ε stand to epsilon or null value in NFA. ε-closures of state qi is the set of states including qi where qi can reach by any number of ε – moves of the given NFA.

ε-closures of qi :-

ε-closures of a state qi, includes qi.

– Set of states reachable from qi on ε – moves.

– Set of states reachable from existing states in ε-closures, using ε-move, and so on.

What is the formal definition of epsilon or ε-closure?
NFA considered for calculation of ε-closures

ε-closures of various states in above figure are given below:

ε-closures of q0 = {q0, q1, q2, q4, q7}

There are ε-moves from q0 to q1 ,
                                         q0 to q7 ,
                                          q1 to q2 ,
                                          q1 to q4 .

ε-closures of q1 = {q1, q2, q4}

There is no ε-moves from q1 to q4 , q1 to q2 .

ε-closures of q2 = {q2}

There are ε-moves from q3 to q6 ,
                                         q6 to q7 ,
                                          q6 to q1 ,
                                          q1 to q2 ,
                                         q1 to q4.

ε-closures of q4 = {q4}

There is no ε-move from q4 .

ε-closures of q5 = {q5, q6, q7, q1, q2, q4}

There are ε-moves from q5 to q6 ,
                                         q6 to q7 ,
                                         q6 to q1 ,
                                        q1 to q2 ,
                                         q1 to q4.

ε-closures of q6 = {q7, q1, q2, q4}

There are ε-moves from q6 to q7 ,
                                        q6 to q1 ,
                                         q1 to q2 ,
                                         q1 to q4.

ε-closures of q7 = {q7}

There is no ε-moves from q7 .

ε-closures of various states are summarized below :

Stateε-closures
q0{q0, q1, q2, q4, q7}
q1{q1, q2, q4}
q2{q2}
q3{q3, q6, q7, q1, q2 ,q4}
q4{q4}
q5{q5, q6, q7, q1, q2 ,q4}
q6{q7, q1, q2 ,q4}
q7{q7}

Recommended:

  1. Introduction to Finite Automata
  2. Deterministic Finite Automata (DFA)
  3. Number of 1’s is a multiple of 3 on {0,1} using DFA
  4. Number of 1’s is not multiple of 3 on {0,1} using DFA
  5. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  6. DFA for number of 0’s divisible by five and 1’s divisible by 3
  7. DFA for All string of length at most five
  8. DFA for All strings ending with abb
  9. DFA for strings in which leftmost symbol differ from rightmost
  10. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  11. Design DFA which accept a binary number divisible by 3
  12. Non-Deterministic finite Automata
  13. Design NFA to accept string containing the substring 0101
  14. Design NFA that accepts string ending with aab
  15. Differentiate between NFA and DFA
  16. Design NFA that start with 01 and end with 10

Leave a Comment

Your email address will not be published. Required fields are marked *

x