TOC : Conversion of Regular Expression (RE) into Finite Automata (FA) | Class-12

📌Highlights: 

Hello friends ! In this post we discuss about how to convert Regular Expression(RE) into Finite Automata (FA). For understanding this method we take so many cases such as how to construct FA if RE is single string a ?, how to construct FA if RE is (R1+R2) ?, how to construct FA if RE is (R1 R2) ?, how to construct FA if RE is (a*) ?how to construct FA if RE is (a⁺) ?how to construct FA if RE is (aa*) ?, what is compliment of FA?.

For converting Regular Expression(RE) into Finite Automata (FA)  let we consider following formats such as :

1. Suppose a be any RE then it FA is :

2. Let R1 be any RE whose FA is M1 and R2 be any RE whose FA is M2, Now We have to construct automata for (R1 + R2)

R1 → M1

R2 → M2

Example:

Suppose we want to construct automata for (0 + 1) it means (0 or 1)

3. Let R1 is any RE its FA is M1 and R2 is any RE whose FA is M2. Now we have to construct automata for (R1 R2)

R1 → M1

R2 → M2

Example :

Suppose we want to construct automata for 01

4. Let a be any RE and we have to construct FA for a*

Example:

Suppose we want to construct automata for a⁺

Suppose we want to construct automata for aa*

Example:

1. Construct a FA for ( 01* + 1)

2. Construct a FA for ( 0+1)*

3. Construct a FA for  ( 0+1)⁺ 

4. Construct a FA for  ( a+b)* abb  
                                        (OR) 
                                   ( a/b)* abb

5. Construct an automata M1
M1

    

Now consider another automata  M2
M2

Suppose R1 is a RE which is accepted by M1 and R2 be any RE which is accepted by M2 than Construct a FA for (R1 U R2)

Solution:

6. Construct an FA which accept string of 0's and 1's does not ends with 00.
Solution:

7. Construct an FA which accept string of 0's and 1's does not contains (101).
Solution:

Let we first assume it will accept 101 string.

But we need that automata which does not accept (101) string, so for this now we make those state as final state who are not final state in above automata.

📗Note: Compliment of FA:

If we change non final state than it is called compliment of FA.

                            or

we can also change final to non-final state.

📌Here is the end of this post friends I hope this post is helpful for you and you all understand about Conversion of Regular Expression (RE) into Finite Automata (FA). We will meet in new post till Thanks!