1 of 26

Session 8: �Equivalence of finite Automaton and regular expressions

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 26

Equivalence of Regular Expression & FA

RE

NFA

DFA

Thompson’s Construction Technique

Set construction algorithm to convert NFA to DFA

Arden’s Theorem or

State Elimination Method

Amity School of Engineering & Technology

3 of 26

Thompson’s Construction Technique

RE to FA Conversion

a

Φ

λ

a

RE

NFA

Amity School of Engineering & Technology

4 of 26

Case 1 : Construction of L₁ + L₂(Union)

Case 2 : Construction of L₁L₂

(Concatenation)

Case 3 : Construction of L₁* (Star closure)

RE to FA Conversion

Amity School of Engineering & Technology

5 of 26

RE to FA Conversion - Example

RE 🡪 01

r₁ = 0

r₂ = 1

r₃ = r₁. r₂

q₀

q₁

0

q₂

q₃

1

q₀

q₁

0

q₂

q₃

1

ε

Amity School of Engineering & Technology

6 of 26

RE to FA Conversion - Example

RE 🡪 01*

r₁ = 0

r₂ = 1

r₃ = r₂*

r₄ = r₁. r₃

q₀

q₁

0

q₂

q₃

1

q₅

q₄

q₂

q₃

1

ε

q₀

q₁

0

q₅

q₄

q₂

q₃

1

ε

Amity School of Engineering & Technology

7 of 26

RE to FA Conversion - Example

RE 🡪 0 + 1

r₁ = 0

r₂ = 1

r₃ = r₁+ r₂

q₀

q₁

0

q₂

q₃

1

q₀

q₁

0

q₂

q₃

1

ε

q₄

q₅

ε

Amity School of Engineering & Technology

8 of 26

RE to FA Conversion – More Example

1*0 + 0

(0+1)*

0*1*

(01)*(10)*+00*

Amity School of Engineering & Technology

9 of 26

Amity School of Engineering & Technology

10 of 26

Amity School of Engineering & Technology

11 of 26

Amity School of Engineering & Technology

12 of 26

Amity School of Engineering & Technology

13 of 26

Methods for Conversion

Conversion using Arden’s Theorem

Conversion using State Elimination Method

Amity School of Engineering & Technology

14 of 26

Arden’s Theorem:

Let P and Q be two regular expressions over ∑. If P does not contain λ, then the following equation in R,

R = Q + RP

has a unique solution given by

R = QP*

Amity School of Engineering & Technology

15 of 26

Construction of FA from RE- Arden’s Theorem

Conditions-

The transition diagram must not have any ∈ transitions.

There must be only a single initial state.

Step-01:

Form equation for each state considering the transitions which comes towards that state.

Add ‘∈’ in the equation of initial state.

Step-02:

Bring final state in the form R = Q + RP to get the required regular expression.

Arden’s Theorem can be used to find a regular expression for both DFA and NFA.

If there exists multiple final states, then-

Write a regular expression for each final state separately.
Add all the regular expressions to get the final regular expression.

Amity School of Engineering & Technology

16 of 26

Example : 1

q₁

q₂

q₃

a

b

a

b

a

Initial Equations

q₁ = q₁a + q₂b + λ

q₂ = q₁a + q₂b +q₃a

q₃ = q₂a

Substituting the value of q₃ in q₂

we get:

q₂ = q₁a + q₂b + q₂ a a

q₂ = q₁a + q₂(b + aa )

By Arden’s Theorem

R = Q + RP has a solution R = QP*

Therefore

q₂ = q₁a(b + aa)*

Amity School of Engineering & Technology

17 of 26

Example : 1

q₁

q₂

q₃

a

b

a

b

a

Substituting the value of q₂ in q₁

we get:

q₁ = q₁a + q1a(b+aa)* b + λ

q1 = q1 (a + a(b+aa)*b) + λ

By Arden’s Theorem

R = Q + RP has a solution R = QP*

Therefore

q₁ = λ (a + a(b+aa)*b )*

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

Substituting the values

q2 = (a+a(b+aa)*b)*a(b+aa)*

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

So the Resultant regular expression that describes the language accepted by the given FA is:

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

Amity School of Engineering & Technology

18 of 26

Example : 2

q₁

q₂

q₄

q₃

b

a

a,b

Initial Equations

q₁ = q₂b + q₃a + λ

q₂ = q₁a

q₃ = q₁b

q₄ = q₂a + q₃b + q₄a + q₄b

Since q1 is the only final state and it involves only q2 and q3 in its equation, the equation q4 is redundant for us.

So we will consider only q2 and q3 to solve q1.

q₁ = q₁ab + q₁ba + λ

= q₁(ab +ba) + λ

By Arden’s Theorem

q₁ = λ (ab + ba)*

So the Resultant Regular Exp is:

(ab + ba)*

Amity School of Engineering & Technology

19 of 26

Example : 3 (Multiple Final States)

q₁

q₂

q₃

0

1

0,1

Initial Equations

q₁ = q₁0 + λ

q₂ = q₁1 + q₂1

q₃ = q₂0 + q₃(0 + 1)

q₁ = λ 0* = 0*

q₂ = q₁ 1 + q₂ 1

q₂ = 0* 1 + q₂ 1

q2 = (0*1)1*

As the Final States are only q₁ and q₂, we need not solve for q₃

Therefore the Regular Expression will be:

q1 + q2 = 0* + 0*(11*)

= 0* (λ + 11*)

= 0*1* (by theorem)

Amity School of Engineering & Technology

20 of 26

Example 4

Amity School of Engineering & Technology

21 of 26

Example 5

Amity School of Engineering & Technology

22 of 26

Example 5…

Amity School of Engineering & Technology

23 of 26

Example 6

Amity School of Engineering & Technology

24 of 26

Example 7

Amity School of Engineering & Technology

25 of 26

Example 7…

Amity School of Engineering & Technology

26 of 26

SUMMARY

Regular Expressions represent the Regular Languages.
RE can be converted to Finite Automata using Thomson’s Method
FA can be converted to RE using Arden’s Method

Amity School of Engineering & Technology