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:


  • 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:






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.