NFA to Regular Expression Conversion and vice versa.

Here we are going to learn how we can convert a given finite machine into a Regular Expression and vice versa.

1. NFA to RE 

To convert a given NFA to RE we have a various method:

  1. State Elimination Method
  2. Algebraic Method
  3. Arden's Theorem.

1. State Elimination Method:

Theory:

  • There should be no incoming edges to initial state, if it has an incoming edge, made a new initial state and give a path to previous intail stages using Epsilon. Example:

      

  • There should be no outgoing edges from the final state if it has then made another final stage and give the path to that using Epsilon. Example:

  • There must be only one final state. Example:

  • Other than the intial and final state, eliminate all state one by one but path should be preserved. 

Some Examples:

 

 

 

Contributor's Info

Created:
0Comment
RE to NFA

 

Some tips:

1. ab:    first you go to a state A using input a then from A you go to state B

2. a + b: you can go to next state either by taking a as input or b as input.

3. (bc)* :  It means bc are in a loop.

Contributor's Info

Created:
0Comment