NFA to Regular Expression

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₁ = ϵ + q₁a + q₂b - (1)

q₂ = q₁a + q₂b + q₃b - (2)

q₃ = q₂a - (3)

Now we will simplify the above equations.

From (3):

q₃ = q₂a

     = (q₁a + q₂b + q₃b)a

     = q₁aa + q₂ba + q₃ba - (4)

From (2):

q₂ = q₁a + q₂b + q₃b

    = q₁a + q₂b + (q₂a)b

    = q₁a + q₂(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₂ = q₁a + q₂(b + ab) is of the form R = Q + RP, where R = q₂, Q = q₁a and P = (b + ab), therefore, we can write it as:

q₂ = q₁a(b + ab)* - (5)

From (1):

q₁ = ϵ + q₁a + q₂b

Putting value of q₂ from equation (5):

q₁ = ϵ + q₁a + (q₁a(b + ab)*)b

q₁ = ϵ + q₁(a + (a(b + ab)*)b

Now, this equation is again of the form R = Q + RP, where R = q₁, Q = ϵ and P = (a + (a(b + ab)*)b.

Therefore, according to Arden’s theorem, we can write it as:

q₁ = ϵ(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₃. 

q₃ = q₂a

Substituting q2 from the equation (5):

q₃ = q₁a(b + ab)*a

Substituting q1 from the equation (6):

q₃ = (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

1. What is an NFA?
   NFA (Non-Deterministic 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.
2. 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.
3. 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*.
4. 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!