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)*