145 views
0 votes
0 votes
Which of the following identities are true for arbitrary regular languages $R$ and $S$. Choose ALL correct answers.
  1. $(R^\ast S^\ast)^{\ast}= (R+S)^{\ast}$
  2. $(RS)^{\ast}R = R(SR)^{\ast}$
  3. $(R+RS)^{\ast} = \left(R^{\ast} +RS^{\ast}\right)^{\ast}$
  4. $(R+S)^{\ast} S = (R^{\ast} S)^{\ast}$

1 Answer

2 votes
2 votes
  1. (a*b*)*=(a+b)* this is a property of a regular expression. So option A is correct.

 

      B.(ab)*a=a(ba)* this is also a property of a regular expression. So option B is correct.

 

      C. LHS, (R + RS)*

         RHS, take R* as ‘a’ and RS* as ‘b’ then it will become (a+b)* = (a*b*)*

         So, (R* + RS*)*=((R*)*(RS*)*)* =  (R*(RS*)*)* = (R + RS*)* .  [(a*)*=a*]

        LHS != RHS. So C false.

 

       D. RHS can generate epsilon(empty string) but LHS can not. So D false.

 

       Correct answers : A,B.

 

    Properties of Regular expressions - GeeksforGeeks 

    Regular expression - Wikipedia

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked Nov 30, 2021
113 views
Kamala tosses $11$ fair coins and Rajani tosses $10$ fair coins. The probability that the number of heads obtained by Kamala is more than the number of tails obtained by ...