##### 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:   ##### 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.