equivalent regular expression?

Question

Assume $R_1$, $R_2$, and $R_3$ are three regular expressions.

Given $R_1 + R_2 \cdot R_3 = (R_1+R_2) \cdot (R_1+R_3)$ for any $R_2$ and $R_3$. Which of the following could be correct condition which always satisfies the above equation.

1. $R_1 = R_2$

2. $R_1 = R_3$

3. $R_1 = \emptyset$

A) only 1 and 2 are correct

B) only 1 and 3 are correct

C) only 2 and 3 are correct

D) 1,2, and 3 are correct

Answer is given as D

Comments

yes i think all should be correct .!

---

Suppose R1 = R2 = ab

R3 = c

Then R1 + R2R3 = ab+abc = ab(Ɛ+c)

But (R1+R2)(R1+R3) =(ab + ab)(ab+c) = ab(ab+c) = abab + abc

What am I doing wrong here?

Answer 1

Let us take cases one by one :

Case 1 :

LHS    =   R₁ + R₂.R₃

          =   R₁  + R₁.R₃

RHS   =   (R₁ + R₂) . (R₁ + R₃)

          =   R₁.( R₁ + R₃)  [ As  R₁ = R₂ given ]

          =   R₁ . R₁  + R₁ . R₃  [ As follows from the distributive property ]

which is not equal to LHS as R₁ . R₁   !=  R₁..Hence (i) is false..

Simlarly we can prove (ii) is also false..

For case (iii) , we have :

LHS   =  R₁ + R₂.R₃

            =   Φ + R₂.R₃

            =   R₂.R₃  [ As R + Φ  = R like additive identity ]

RHS   =  (R₁ + R₂) . (R₁ + R₃)

         =  ( Φ + R₂) . ( Φ + R₃)

         =   R₂.R₃ [ As R + Φ  = R like additive identity ]

Hence only (iii) is true

So none of the options of the given question is true..

Comments

Thanks man.

Answer 2

(R1+R2) (R1+R3) = R1R1 + R1R3 + R2R1 + R2R3

Now, R1 = R2 => LHS = R1 + R2R3 = R1 + R1R3
RHS = R1R1 + R1R3 + R1R1 + R1R1

So, they are not equal. For example consider R1 = R2 = a, R3 = b. LHS = a + ab, RHS = aa + ab

When R1 = R3, LHS = R1 + R2R1
RHS = R1R1 + R1R1 + R2R1 + R2R1, again not equal. For example, R1 = R3 = a, R2 = b, LHS = a + ba, RHS = aa + ba

When R1 = ϕ,

LHS = ϕ + R2.R3 = R2.R3
RHS = (ϕ + R2).(ϕ + R3) = R2.R3, hence equal.

Comments

so , here no option matches , right ?

---

yes.

---

A slight correction.

When R1 = ϕ,
LHS = ϕ + R2.R3 = R2.R3
RHS = (ϕ + R2).(ϕ + R3) = R2.R3 hence equal.

---

Thanks :)