MadeEasy Test Series: Theory Of Computation - Regular Expressions

Question

Let x,y,z be regular expression.Let L1,L2 and L3 be regular expression defined as follows:

L1=(x*y)*x*y

L2=(x*y)(x*y)*

L3=x*y(yx*)*y

Find the relation between L1, L2 and L3?

I solve such problems by finding strings which one of the language can have and other cannot. But sometimes I get messed up doing so, is there any better approach to solve such questions? Help Please!

Comments

@MiNiPanda @Shaik Masthan @eyeamgj @Gupta731 

---

@Shivam Kasat

Please copy the options here..

---

L1=(x*y)*x*y

L2=(x*y)(x*y)*

L3=x*y(yx*)*y
 

check 1 and 2, ( assume x*y = R )

L1 = (x*y)*x*y = (x*y)* (x*y) = R* . R = R$^+$ = (x*y)$^+$

L2=(x*y) (x*y)* = R.R* = R$^+$

 

check 1 and 3

shifting rule :- (r.s)* r = r.(s.r)*  where r and s are regular expressions

L3=x*y(yx*)*y = x*y . y . (x*.y)* = R . y .R*

L1 = R. R* = (x*y) . (x*y)*

now easily you can understood the relation between L1 and L3

---

 

Sorry! I messed up with the languages they have given in the test ! But I got the approach @Shaik Masthan Thanks

---

@Shaik Masthan Can you please provide me some link where I can read out these transformation rules!

---

@Shivam Kasat

You can prove that rule by yourself only:

(r.s)*r =rsrsrsrs....rs r = r(srsrsr....s r)= r.(s.r)*

---

@Shaik Masthan-Sorry for asking such basic question, but how did you apply that rule to L3?

I am weak at this portion.

---

L3=x*y(yx*)*y = x*y . y . (x*.y)* = R . y .R*

How did you get this Bold portion?

I understood the part $(rs)^*r=r(sr)^*$

---

given that L$_3$ = x*y(yx*)*y = $\color{red}{x^*y}\color{green}{(yx^*)^*y}$ = $\color{red}{x^*y}\color{green}{y(x^*y)^*}$ = $\color{}{x^*y}\;\color{green}{y}\;{(x^*y)^*}$

---

Thanks :)