Conversion of Finite Automata to Regular Expressions

Conversion of Finite Automata to Regular Expressions

AU Dec.-03,04,05,09,11,13,16,19, May-05,06,07,08, 12, Marks 16

The Arden's theorem is useful for checking the equivalence of two regular expression as well as in conversion of DFA to r.e. Let us see its use in conversion of DFA to r.e.

Following algorithm is used to build the r.e. from given DFA.

1. Let q₁ be the initial state.

2. There are q₂, q₃, q₄, ...q_n number of states. The final state may be some q_j where j ≤ n.

3. Let α_ji represents the transition from q_j to q_i

4. Calculate q_j such that

q_i = α_ji q_j

If q_i is a start state

to qi

q_i = α_ji q_j + ε

5. Similarly compute the final state which ultimately gives the regular expression r.

Let us solve few examples based on this algorithm.

Example 2.4.1 Construct r.e. from given DFA.

Solution: Let us write down the equations state on

q₁ = q₁ a + ε

Since q₁ is a start state ε will be added and the input a is coming to q₁ from q₁ hence we write

State = Input coming to it × Source state of input

Similarly q₂ = q₁ a + q₂ b

Let us simplify q₁ first

q₁ = q₁ a + ε

We can re-write it as

q₁ = ε + q₁ a

which is similar to R = Q + RP which further gets reduced to R = QP*.

Assuming R = q₁, Q = ε, p = a

We get

q₁ = ε . a*

q₁ = a*

ε R = R

Substituting value of q₁ in q₂ we get

q₂ = q₁ b + q₂ b

q₂ = a * b + q₂ b

We can compare this equation with R = Q + R P assuming R = q₂, Q = a*b, P = b which gets reduced to R = QP*.

q₂ = a*b.b*

As R R* = R⁺

q₂ = a*.b⁺

From the given DFA, if we want to find out the regular expression, we normally calculate the equation for final state. Since in the given DFA q₂ is a final state and q₂ = a*b⁺. We can conclude as the DFA represents a as regular expression.

Example 2.4.2 Represent the language accepted by following DFA.

Solution: Since there is only one state in the finite automata let us solve for q₀ only.

q₀ = q₀0 + q₀1 + ε

q₀ = q₀ (0+1) + ε

= ε . (0+1)^*      R = Q + R P

q₀ = (0+1)^*

Since q₀ is a final state, q₀ represents the final r.e. as

r = (0 + 1)*

L (r) = {ε, 0,00,1,11,10,....}

L (r) = {any combination of 0 and 1}

Example 2.4.3 Construct r.e. for the given DFA. AU May-07, Marks 6

Solution: Let us build the regular expression for each state.

q₁ = q₁0 + ε

q₂ = q₁1 + q₂1

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

Since final states are q₁ and q₂, we are interested in solving q₁ and q₂ only.

Let us see q₁ first

q₁ = ε + q₁0

Which is R = Q + R P equivalent so we can write

q₁ = ε .(0)^*

q₁ = 0^*

ε. R = R

Substituting this value into q₂, we will get

q₂ = 0*1 + q₂1

q₂ = 0*1 (1)^*     R = Q + R P ⇒ Q P^*

The regular expression is given by

r = q₁ + q₂ =0^* + 0^* 1. 1^*

r = 0^* + 0^* 1⁺             1.1^* = 1⁺

Example 2.4.4 Convert the following NFA into a regular expression. AU: Dec.-13, Marks 8

Solution: We will obtain regular expression using Arden's method.

The equations for each state are -

A = A0 + A1 + ε = A(0 + 1) + ε

B = A1

C = B (0+1)

D = C (0+1)

We will solve equation (1)

A = A (0+1) + ε

i) R = RP + Q gives R = QP^* ii) εR^* = R^*

A = ε(0+1)^* = (0+1)^*

A = (0+1)^* … (5)

Equation (2) becomes

B = A1 = (0+1)^* 1 … (6)

Now by using equation (6) we get equation (3) as

C = B (0+1)

C = (0+1)* 1 (0+1) … (7)

Using equation (7), we get equation (4) as

D = C (0+1)

= (0+1)* 1 (0+1) (0+1) … (8)

As state C and D are final states equation (7) and equation (8) represent final regular expression.

r.e. [(0+1)^* 1 (0 + 1)] + [(0+1)^* 1 (0 + 1) (0 + 1)]

Example 2.4.5 Construct the regular expression corresponding to the state diagram given in the following Fig. 2.4.5. AU: May-05, Marks 10; May-08, Marks 16, Dec.-19, Marks 2

Solution: We will obtain the regular expression for the given state diagram using Arden's theorem. Let us write equations for each state.

q₁ = q₁0 + q₃0 + ε being a start state, add ɛ.

q₂ = q₁1 + q₂1 + q₃1

q₃ = q₂0

Consider q₂ first.

q₂ = q₁1 + q₂1 + q₃1

q₂ = q₁1 + q₂1 + q₂01      q₃ = q₂0

q₂ = q₂ (1+01) + q₁1

R = Q + RP gives R = QP^*

R = q₂, Q = q₁1, P = (1 + 01)

q₂ = q₁1 (1+01)^*

Then put value of q₂ in q₃ and we get,

q₃ = q₁1 (1+01)^* 0

Now substitute value of q₃ in q₁

q₁ = q₁0 + q₃0 + ε

q₁ = q₁0 + q₁1 (1+01)^* 00 + ε

q1 = q₁ [0+1 (1+01)^* 00] + ε

R = Q + RP gives R = QP^*

R = q1, Q = ε, P = 0+1 (1+01)^* 00 we get

q₁ = ε [0+1 (1+01)^* 00]^*

q₁ = (0+1 (1+01)^* 00)*             ε R = R

State q₁ is a final state. Hence an equation for final state becomes a regular expression for given state diagram.

The r.e. = (0+1 (1+01)* 00)*

Example 2.4.6 Obtain the regular expression for the finite automata. AU: May-12, Marks 8

Solution: We will write the equations for each state,

q₁ = q₁ a + ε … (1)

q₂ = q₂a + q₁b … (2)

q₃ = q₂b … (3)

Solving equation (1)

q₁ = q₁ a + ε

q₁ = ε a^* = a^*

R = Q + RP

gives R = QP*

and ε R^* = R^*

Solving equation (2) using q₁ = a^* we get,

q₂ = q₂ a + a^* b

q₂ = a^* b a^*

Solving q₃ by putting q₂ = a^* b a^*

we get

q₃ = q₂ b

q₃ = a^* ba^* b

As q₃ represents the final state, the equation for state q₃ represents the regular expression. Hence regular expression = a^* ba^* b.

Review Questions

1. State and explain the conversion of DFA into regular expression using Arden's theorem. Illustrate with an example. AU: Dec.-11, Marks 16

2. Discuss the basic approach to convert from NFA to regular expression. Illustrate with an example. AU Dec.-16, Marks 16