TOC : Conversion of Finite Automata (FA) to Regular Expression(RE) | Class-13

📌Highlights: 

Hello Friends ! In this post we learn about the Conversion of Finite Automata (FA) to Regular Expression(RE). In this post we cover following such as Identity Rules, Arden's Theorem, By the help of Identity rules and Arden's Theorem how we convert finite automata(FA) to regular expression(RE) with the help of examples .

For converting Finite Automata (FA) to Regular Expression (RE) we must remember some identity rules of (RE):

Suppose R be any RE

Identity Rules are :

    1. ∈ + RR* = ∈ + R*R =R*

    2. ∈R = R∈ = R

    3. φ + R = R + φ = R

    4. φ R = R φ = φ

    5. P ( Q P )* = ( P Q )* P

    6. ( P  + Q )* = ( P*  + Q* )*

Now one more thing need to be remember i.e Arden's Theorems

Arden's Theorem:

Let P and Q be two RE where P does not contain ∈ and if we have a equation of the form

    R = Q + R P        : where R be any state

Then its state can be written as 

    R = Q P*

Example:

In the above automata there are two edges, the level of first edge is 'a' and those edge which have no level is assumed as ∈.

So,

    q1 =q1 a + ∈ --------- 1 equation

Then apply Arden's Result  in equation 1

we get,

    q1 = ∈ a*

    q1 = a*

Above expression explain q1 accept RE 'a'

q1 is final state and which accept 'a' so, it is a final answer.

Now we will do some questions for better understand.

Question 1:

    q1 = q1  0 + ∈          -------  1st equation

    q2 = q2  1 + q1  1    -------- 2nd equation

We want to create RE for q2 apply Arden's result in equation -1

 we get

    q1  = ∈ 0*

    q1  =  0*

Now Put the value of q1 in equation -2

    q2 = q2   1  + 0* 1 ------- 3rd equation

Now Apply Arden's  result in equation -3

we get

    q2 = 0* 1 1*

Question 2:

If we have two final state we use either q1  or  q2.

    q1 = q1  0  +  ∈

    q1 = ∈ 0*

    q1 = 0*

    q2 = q2  1 +  q1  1

    q2 =  q2  1 + 0* 1

    q2 =  0* 1  1*

    RE =  0* + 0* 1  1*

By using identity

     = 0* ( ∈ + 0* 1 1* )

     = 0* 1*

So the final RE is 0* 1*

Question 3:

    q1 = q2 b + q3 a + ∈   ------------ 1st equation

    q2 = a1 a  ----------------------- 2nd equation

    q3 = q1 b  ----------------------- 3rd equation

    q4 = q4 a b + q2 a + q3 b ----- 4th equation

Now put the value of q2 and q3 in equation -1

we get

    q1 = q1 a b  + q1 b a  + ∈

    q1 = q1 ( a b + b a ) + ∈ --------- 5th equation

Now Apply Arden's result

we get

    q1 = ∈ (a b + b a)*

    q1 = (a b + b a)*

Since here only one final state i.e q1

So Regular Expression(RE) of Finite Automata(FA)  is (a b + b a)*

Question 4:

Construct RE accepted by this FA.

    q1 = q1 a + q2 b + ∈  ------------------- 1st equation

    q2 = q2 b + q1 a + q3 a -----------------2nd equation

    q3 = q2 a  ---------------------------------3rd equation

Now put the value q3 in equation -2

    q2 = q2 b + q1 a + q2 a a

    q2 =q2 ( b + a ) + q1 a a

Now apply Arden's result

Note : 

If all state are interdependent then Q may contain at least one state.

    q2 = q1 a (b + a a)*   ------------------- 4th equation

Put the value of q2 in q1 or equation -1

we get

    q1 = q1 a + q1 a (b + a  a)* b + ∈

Now apply Arden's result

    q1 = q1  (b + a  a)* b + ∈

    q1 = (a + a (b + a  a)* b)* ---------------------- 5th equation

Substitute the value of q1 in equation -4

    q2 = (a + a (b + a  a)* b)* a (b + a  a)*  ---------- 6th equation

Put the value of q2 in equation -3

    q3 = (a + a (b + a  a)* b)* a (b + a  a)* a

So regular expression(RE) of FA is 

    (a + a (b + a  a)* b)* a (b + a  a)* a

This is the end of this post, I hope you understand how to convert any Finite Automata (FA) to Regular Expression(RE), I also given so many examples to clear more. I hope this post is useful for you all. We will meet in next post till..Thanx !