Eliminating Epsilon transition (ε-Transitions) | Conversion of Epsilon-NFA to DFA | Conversion of Epsilon-NFA to NFA | Theory Of Computation (TOC)


Theory Of Computation (TOC) | Eliminating Epsilon Transition(ε-Transitions):

Given any Epsilon NFA (ε-NFA) , we can find a DFA D that accepts the same language as E. The construction is close to the subset construction, as the states of D are subsets of the states of E. The only difference is that dealing with ε-transitions, which can be done by using ε-closure.


Epsilon NFA (ε-NFA) - DFA:
Let E = (QE,∑, 𝛿E,qo, FE) is ε-NFA. The DFA equivalent to given ε-NFA is constructed as:

D = (QD,∑, 𝛿D,qD, FD)

 Where,
QD= set of subsets of QE i.e QD ⊆ 2ᣔQE
qD=ε-closure(qo)
FD = set of states that contains at least one accepting state of E.
i.e. FD= {S|S is in qD and S∩FE∉φ}.
𝛿D (S, a) is computed, for all a in ∑ and sets S in QD by:


  • Let 𝛿cap(q, x) = {p1, p2,......, pk} i.e. pi ’s are the states that can be reached from q following path labeled x which can end with many ε & can have many ε.
  • Compute

  • Then,


For Example:

Conversion of Epsilon-NFA to DFA

Given an ε-NFA as:





Transition Diagram:

ε-NFA —NFA:

Let E = (QE,∑, 𝛿E,qo, FE) is ε-NFA. The NFA equivalent to given ε-NFA is constructed as:
N = (QN,∑, 𝛿N,qN, FN)
  • Start state of NFA =Start state of ε-NFA i.e. qN= qo
  • QN= set of subsets of QE i.e QN ⊆ QE
  • For any state q  ∈ QN and a ∈ Σ:
𝛿N(q, a) = ε-closure (𝛿E(ε- closure(q), a))
  • FN= { q ∈ QN: ε- closure(q) ∩FE≠φ}


For Example:

Given an ε-NFA as:


Transition Table:

Transition Diagram:

Comments

Post a Comment

Subscribe Us and Thanks for visiting blog.

Popular posts from this blog

C Program for SCAN Disk Scheduling Algorithm | C Programming

Image
Introduction to SCAN disk scheduling :                    In the SCAN algorithm, the disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of the head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk. The SCAN algorithm is sometimes called the elevator algorithm, since the disk arm behaves just like an elevator in a building, first servicing all the requests going up and then reversing to service requests the other way.
Read more

C program to Find Cartesian Product of Two Sets | C programming

Image
C program to find the Cartesian Product of two sets   Cartesian product  is a mathematical operation that returns a set (or  product set  or simply  product ) from multiple sets. That is, for sets  A  and  B , the Cartesian product  A  ×  B  is the set of all ordered pairs  ( a ,  b )  where  a  ∈  A  and  b  ∈  B . Products can be specified using set-builder notation, e.g. {\displaystyle A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.}
Read more

C Program To Check The String Is Valid Identifier Or Not | C Programming

Image
C Program To Check The String Is Valid Identifier Or Not #include <stdio.h> #include <conio.h> #include <string.h> int main () { char string [ 25 ]; int count= 0 ,flag; printf ( "Enter any string: " ); gets (string); if ( ( string [ 0 ]>= 'a' && string [ 0 ]<= 'z' )||( string [ 0 ]>= 'A' && string [ 0 ]<= 'Z' )||( string [ 0 ]== '_' )) {     for ( int i= 1 ;i<= strlen (string);i++)     {         if (( string [i]>= 'a' && string [i]<= 'z' )||( string [i]>= 'A' && string [i]<= 'Z' )||( string [i]>= '0' && string [i]<= '9' )||( string [i]== '-' ))     {     count++;     }        }     if (count== strlen (string))     {       flag= 0 ;     } } else {     flag= 1 ; } if (flag== 1 )     printf ( " %s is not valid identifier" ,string); else     printf ( " %s is valid ident
Read more