Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Steps To Convert Regular Expressions To Finite Automata
3.
Examples
4.
Frequently Asked Questions
4.1.
Are null values accepted in DFA?
4.2.
Which Automata is used in Lexical Analysis in Compilers?
4.3.
What does Φ signify in a regular expression?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Conversion Of Regular Expressions to Finite Automata

Author Rajat Agrawal
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Converting a regular expression to a finite automaton means turning a pattern description into a step-by-step machine that checks if a string fits that pattern. It's like creating a specialized robot that follows the rules of the pattern to see if a string matches.

Regular Expressions are the expressions that describe the language accepted by Finite Automata. It is the most efficient way to represent any language.

We can easily convert the Regular expressions (also check out some examples of regular expressions)to Finite automata.

Let’s understand the steps required to convert the Regular expressions to Finite automata.

Also See, Moore Machine

Steps To Convert Regular Expressions To Finite Automata

To convert the RE to FA, the method that is popularly used is known as the Subset method. This method is used to get FA from the given regular expression

The steps in this method are given below:-

Step 1: Make a transition diagram for a given regular expression, using NFA with ε moves.

Step 2: Then, Convert this NFA with ε to NFA without ε.

Step 3: Finally, Convert the obtained NFA to equivalent DFA.

Some standard rules help in the conversion of RE to NFA are:-

1.) If RE is in the form a+b, it can be represented as:

RE a+b

 

2.) If RE is in the form ab, it can be represented as:

RE ab

 

3.) If RE is in the form of a*, it can be represented as:

RE a*

In the next section, we will implement the above method to convert the RE to FA.

Also read -  arden's theorem

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

Examples

Example 1: Design a Finite Automata from the given RE [ ab + (b + aa)b* a ].

Solution. At first, we will design the Transition diagram for the given expression.

Step 1: 

Step 1

Step 2:

Step 2

Step 3:

Step 3

Step 4:

Step 4

Step 5:

Step 5

After step 5, we have got NFA without ε. Now we will convert it into the required DFA; we will first write a transition table for this NFA.

Transition Table For NFA:

Transition Table For NFA

The Corresponding transition table for DFA is:

transition table for DFA

Example 2: Design an NFA from the given RE [ a (a* ba* ba*)* ].

Solution. The Transition diagram that represents the NFA of the above expression is as follow:

Step 1:

Step 1

Step 2:

Step 2

Step 3:

Step 3

We have successfully converted the given RE to an NFA.

Also see, Turing Machine in TOC.

Frequently Asked Questions

Are null values accepted in DFA?

No, the null values are not accepted in DFA.

Which Automata is used in Lexical Analysis in Compilers?

DFA is used in Lexical analysis in compilers.

What does Φ signify in a regular expression?

Φ is a regular expression that denotes the empty set.

Conclusion

In this blog, we have discussed how to convert regular Expression to Finite Automata. Converting regular expressions into finite automata is like turning patterns into machines that can recognize words. This process helps programmers build tools for finding specific text patterns and understanding languages better. 

Recommended Readings


Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Happy Learning!!

Previous article
Examples of Regular Expression
Next article
Regular Expression IN TOC
Live masterclass