Equivalence of Two Regular Expressions

Equivalence of Two Regular Expressions 

AU May-10,11, Marks 9

The two regular expressions P and Q are equivalent (denoted as P = Q) if and only if P represents the same set of strings as Q does. For showing this equivalence of regular expressions we need to show some identities of regular expressions.

Let P, Q and R are regular expressions then the identity rules are as given below

1. ε R = R ε = R

2. ε^* = ε       ε is null string

3. (ϕ)^* = ε       ϕ is empty string.

4. ϕ R = R ϕ = ϕ

5. ϕ + R = R

6. R + R = R

7. RR^* = R^*R = R⁺

8. (R^*)^* = R^*

9. ε + RR^* = R^*

10. (P+Q) R = PR + QR

11. (P+Q)^* = (P^* Q^*) = (P^* + Q^*)^*

12. R^* (ε + R) = (ε + R) R^* = R^*

13. (R + ε)^* = R^*

14. ε + R^* = R^*

15. (PQ)^* P = P (QP)^*

16. R^* R + R = R^* R

Let us see one important theorem named Arden's Theorem which helps in checking the equivalence of two regular expressions.

Arden's Theorem: Let, P and Q be the two regular expressions over the input set 2. The regular expression R is given as

R = Q + RP

Which has a unique solution as R = QP^*.

Proof : Let, P and Q are two regular expressions over the input string Σ.

If P does not contain & then there exists R such that

R = Q + RP        …. (2.5.1)

We will replace R by QP^* in equation (2.5.1)

Consider R.H.S. of equation (2.5.1)

= Q + QP^* P

= Q(ε + P^* P)

= QP^*

ε + R^* R = R^*

Thus      R = QP^*

is proved. To prove that R = QP^* is a unique solution, we will now replace L.H.S. of equation (2.5.1) by Q + RP. Then it becomes

Q + RP

But again R can be replaced by Q + RP.

Q + RP = Q + (Q + RP) P

= Q + QP + RP²

Again replace R by Q + RP.

= Q + QP + (Q + RP) P²

= Q + QP + QP² + RP³

Thus if we go on replacing R by Q + RP then we get, Q + RP = Q + QP + QP² + ... + QPⁱ + Rpⁱ⁺¹

= Q(ε + P+ P² + ….. Pⁱ) + Rpⁱ⁺¹

From equation (2.5.1),

R = Q (ε + P+ P² + ….. + Pⁱ) + Rpⁱ⁺¹ …. (2.5.2)

Where  i ≥ 0

Consider equation (2.5.2),

R = Q(ε + P+ P² + ... + Pⁱ + RPⁱ⁺¹ /p*

R = QP^* + RPⁱ⁺¹

Let w be a string of length i.

In RPⁱ⁺¹ has no string of less than i + 1 length. Hence w is not in set RPⁱ⁺¹. Hence R and QP^* represent the same set. Hence it is proved that

R = Q + RP has a unique solution.

R = QP^*

Example 2.5.1 Prove (1+00*1) + (1+00*1) (0+10*1) * (0+10*1) = 0*1(0+10*1) *AU: May-11, Marks 8

Solution: Let us solve L.H.S. first,

(1+00*1) + (1+00*1) (0+10*1) * (0+10*1)

We will take (1+00*1) as a common factor

1+00*1

(ε+(0+10*1)*(0+10*1))

(ε+ R*R) where R = (0+10*1)

As we know, (ε + R^*R) = (ε + RR^*) = R^*

(1+00*1) ((0+10*1)*) out of this consider

(1+00*1) (0+10*1)*

Taking 1 as a common factor

(ε+00*) 1 (0+10*1) *

Applying ε + 00* = 0*

0*1 (0+10*1) *

= R.H.S.

Hence the two regular expressions are equivalent.

Example 2.5.2 Show that (0*1*)* = (0+1)*

Solution: Consider L.H.S.

= (0*1*)*

{ε, 0,00,1,11,111, 01, 10,...}

= {any combination of O's, any combination of 1's, any combination of 0 and 1, ε}

Similarly,

R.H.S.

= (0+1)*

= {ε, 0, 00, 1, 11, 111, 01, 10,....}

= {ε, any combination of 0's, any combination of 1's, any combination of 0 and 1}

Hence, L.H.S. = R.H.S. is proved.

Example 2.5.3 Prove that r (s+t) = rs + rt

Solution: In case of L.H.S.

L.H.S. = r (s+t) solving this further

= r.s + r.t

i.e. r is concatenated with s or with t

= R.H.S.

L.H.S. = R.H.S. is proved.

Check for the following regular expressions for equivalence and justify.

i) R₁ = [(a + bb)^* (b + aa)^*]^*

ii) R₂ = (a + b)^*

Here R₁ and R₂ are equivalent because the strings which can be generated by R1 can be generated by R₂ or vice versa.

For instance,

R₁ = abab - this string can be generated by selecting a from (a + bb)^* then b from

(b + aa)^* again a from (a + bb)^* and b from (b + aa)^*.

R₂ = abab - this sting can be selecting a then b repetitively from (a + b)^*

Thus R₁ R₂ is proved

ii) R₁ = (a + b)^* abab^*

R₂ = b^* a (a + b)^* ab^*

Here strings generated by R₁ are same as R₂

For instance R₁ can generate abababb. Similarly R₂ can generate abababb as we will select 'null' from b^* then 'null' 'a'; then 'bab' from (a + b)^* then 'abb' from ab^*

Thus

R₁ = R₂ is proved.

Example 2.5.4 Prove ε + 1^* (011)^* (1^* (011)^*)^* = (1 + 011)^*

Solution: Let, L.H.S. is

ε + 1^*(011)^* (1^* (011)^*)^*

If we consider 1^*(011)^* as P₁ then,

= ε + P₁ P₁^*            ε + P₁P₁^* = P₁^*

= P₁^*

We can put P₁ = 1^* (011)^* then,

= (1^*(011)^*)^*

Now consider P₂ = 1 and P₃ = (011) then it becomes

= (P₂^* P₃^*)^*            (P^* Q^*)^* = (P + Q)^*

= (P₂ + P₃)^*            

= (1 + 011)^*

= R.H.S.

Thus   L.H.S. = R.H.S.

Hence

ε + 1^* (011)^* (1^* (011)^*)^* = (1+011)^* is proved.