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:
- State Elimination Method
- Algebraic Method
- 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.