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.

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

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