Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm
3.
Example
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

NFA to Regular Expression

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

NFA (Non-Deterministic Finite Automata) is a state machine used to validate an input string using state transitions. Regular expressions are a sequence of characters that are used to check if the given string follows the pattern or not. Both NFA and regular expressions can be used to define a regular language. In this article, we will see how to convert a given NFA to a regular expression.

You can also read about - Simplification of CFG

Algorithm

Let there be an NFA with N states. Our task is to convert NFA to a regular expression. To do this, we will write equations for each state of the given NFA in the form:

q1 = q1a11 + q2a21 + q3a31 + … qnan1

q2 = q1a12 + q2a22 + q3a32 + … qnan2

qn = q1a1n + q2a2n + q3a3n + … qnann

In the above equations, qi is a state variable corresponding to the ith state, and aij is a set of input symbols.

After this, we try to represent qi in terms of aij using arden's theorem and substituting the state variables. To convert the NFA to a regular expression, we then take the union of all the state variables corresponding to the final states.

You can also read about - Moore Machine

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

q1 = ϵ + q1a + q2b - (1)

q2 = q1a + q2b + q3b - (2)

q3 = q2a - (3)

Now we will simplify the above equations.

From (3):

q3 = q2a

     = (q1a + q2b + q3b)a

     = q1aa + q2ba + q3ba - (4)

From (2):

q2 = q1a + q2b + q3b

    = q1a + q2b + (q2a)b

    = q1a + q2(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*. 

q2 = q1a + q2(b + ab) is of the form R = Q + RP, where R = q2, Q = q1a and P = (b + ab), therefore, we can write it as:

q2 = q1a(b + ab)* - (5)

From (1):

q1 = ϵ + q1a + q2b

Putting value of q2 from equation (5):

q1 = ϵ + q1a + (q1a(b + ab)*)b

q1 = ϵ + q1(a + (a(b + ab)*)b

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

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

q1 = ϵ(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 q3

q3 = q2a

Substituting q2 from the equation (5):

q3 = q1a(b + ab)*a

Substituting q1 from the equation (6):

q3 = (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!

Previous article
Arden's Theorem
Next article
DFA to Regular Expression Conversion
Live masterclass