Equivalence of Two Regular Expressions

For Complete YouTube Video: Click Here

In this class, We discuss Equivalence of Two Regular Expressions.

The reader should have prior knowledge of identity rules of regular expressions. Click Here.

Given expression: (1 + 00*1) + (1 + 00*1)(1 + 10*1)*(1 + 10*1) = 0*1(0 +10*1)*

We need to show the above LHS expression is equal to RHS expression.

We use identity rules to reduce the LHS expression to RHS.

Take (1 + 00*1) as common

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

The above equation is of type (ε + R*R) where R = (1 + 00*1).

(ε + R*R) can be written as R*

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

Take 1 as common

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

(ε + 00*) can be written 0*

0*1(1 + 10*1)*

LHS = RHS

Example 2:

((00*(01)*0) + 0*(10)*)* = (0 + 10)*

From the identity rules (ab)*a = a(ba)*

Substitute the identity rule in the given equation.

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

We take (10)* common

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

We take (00*0 + 0*) as 0*

What ever the strings generated by 00*0 can be generated by 0*.

(0*(10)*)*

We use the identity rule (A + B)* = (A*B*)*

we write (0 + 10)*