Example
Consider the following NFA:
The above NFA has 3 states  q1, q2, q3. To convert this NFA to a regular expression, we will first write the equations of all the states:
q_{1} = Ďµ + q_{1}a + q_{2}b  (1)
q_{2} = q_{1}a + q_{2}b + q_{3}b  (2)
q_{3} = q_{2}a  (3)
Now we will simplify the above equations.
From (3):
q_{3} = q_{2}a
= (q_{1}a + q_{2}b + q_{3}b)a
= q_{1}aa + q_{2}ba + q_{3}ba  (4)
From (2):
q_{2} = q_{1}a + q_{2}b + q_{3}b
= q_{1}a + q_{2}b + (q_{2}a)b
= q_{1}a + q_{2}(b + ab)
According to Ardenâ€™s theorem, whenever we have an equation of the form R = Q + RP, it can be written as R = QP*.
q_{2} = q_{1}a + q_{2}(b + ab) is of the form R = Q + RP, where R = q_{2}, Q = q_{1}a and P = (b + ab), therefore, we can write it as:
q_{2} = q_{1}a(b + ab)*  (5)
From (1):
q_{1} = Ďµ + q_{1}a + q_{2}b
Putting value of q_{2} from equation (5):
q_{1} = Ďµ + q_{1}a + (q_{1}a(b + ab)*)b
q_{1} = Ďµ + q_{1}(a + (a(b + ab)*)b
Now, this equation is again of the form R = Q + RP, where R = q_{1}, Q = Ďµ and P = (a + (a(b + ab)*)b.
Therefore, according to Ardenâ€™s theorem, we can write it as:
q_{1} = Ďµ(a + (a(b + ab)*)b)*
= (a + (a(b + ab)*)b)* [From identity eq.: ĎµR = R]  (6)
The last step is to substitute these values in the final state. The final state for the given example is q_{3}.
q_{3} = q_{2}a
Substituting q2 from the equation (5):
q_{3} = q_{1}a(b + ab)*a
Substituting q1 from the equation (6):
q_{3} = (a + (a(b + ab)*)b)* a(b + ab)*a
We can see that now the equation is represented as a combination of the input symbols a and b only. Thus we have converted the given NFA to a regular expression.
Also see, Turing Machine in TOC.
FAQs

What is an NFA?
NFA (NonDeterministic Finite Automata) is a state machine used to validate an input string using state transitions. In NFA, multiple paths can exist from the current state to the next state for an input symbol.

What are regular expressions?
Regular expressions are a sequence of characters that are used to check if the given string follows the pattern or not.

What is Ardenâ€™s Theorem?
According to Ardenâ€™s theorem, if an expression is of the form R = Q + RP, we can write it as R = QP*.

How to convert a given NFA to a regular expression?
To convert an NFA to a regular expression, we first write equations for each state of the NFA. Then we substitute the state variables using Ardenâ€™s theorem. To get the final regular expression, we take the union of all the final states.
Key Takeaways
In this article, we learned to convert a given NFA to a regular expression using Ardenâ€™s theorem. We also saw a detailed example of converting NFA to a regular expression.
Check out this problem  Shortest Common Supersequence and Symbol Table Operations
Check out this article  Converting NFA to DFA
We hope that this blog has helped you enhance your knowledge of syntax analysis and if you would like to learn more, check out our articles on code studio. Do upvote our blog to help other ninjas grow. Happy Coding!