The Gateway to Computer Science Excellence

+25 votes

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Which of the following regular expression identities is/are TRUE?

- $r^{(^*)} =r^*$
- $(r^*s^*)=(r+s)^*$
- $(r+s)^* = r^* + s^*$
- $r^*s^* = r^*+s^*$

+4

u have problem in r(*) right?

take an example a(a*) where the strings are {a,aa,aaa....}

Similarly r(*) where * is separate from r, it cannot accept epsilon

but r* can accept epsilon too

take an example a(a*) where the strings are {a,aa,aaa....}

Similarly r(*) where * is separate from r, it cannot accept epsilon

but r* can accept epsilon too

0

if r=a(a*)

a(a*)(*) in this what is the meaning of **concatenation of * with a(a*)** .what does it represent?

+1

a(a*) and a(a*)(*) same

but similarly (a+b)* and (a*b*)* are both similar

those are not contradictory

but similarly (a+b)* and (a*b*)* are both similar

those are not contradictory

+37 votes

Best answer

- is the answer
- RHS generates $\Sigma^*$ while LHS can't generate strings where $r$ comes after $s$ like $sr, srr$ etc. LHS $\subset$ RHS.
- LHS generates $\Sigma^*$ while RHS can't generate strings where $r$ comes after an $s$. RHS $\subset$ LHS.
- LHS contains all strings where after an $s$, no $r$ comes. RHS contains all strings of either $r$ or $s$ but no combination of them. So, RHS $\subset$ LHS.

+1

Can you please give any source which contain *r*(*)=*r*.Previous year question book gave answer b*

*and their b is *(*r***s****)*=(*r*+*s*)*

+2

http://gateforum.com/wp-content/uploads/2013/01/CS-1992.pdf

search question no (XVII)

(*r***s****)*=(*r*+*s*)* but in case of (*r***s****) != (*r*+*s*)*

+2

@Anu No. I don't have a proof. In fact I choose i only because all other options are false. In case (b) is with a *, I would choose (b) as there is ambuiguity over (a). I doubt if they meant (empty string*) with (*) in which case (a) is false.

+9

**** Disclaimer : I am not sure that its right or wrong . So if its wrong please don`t blame me :P

I think *r*(∗) != *r*∗ ,

let take a example A(B*) . In this case (B*) will be evaluated first because its with in the bracket . And now consider this R(*) then (*) will be evaluated first but it contain only ∅ and ∅*= ∈ . So R.(∈) = R . peace

+3

^But why you took {}* and not $\epsilon^*$ ? That seems more appropriate. $\epsilon^* = \epsilon$, so answer would still be same.

+3

yes answer might be same but i think ( for safety purpose i say " i think " what if i got wrong :D ) it`s not right thing to do .

suppose L= {} this language means two things either there is no final state or final state is unreachable from initial state .

And for L={∈} this language means without any input we can reach the final state ,So ∅ and ∈ is very much different . But in this case ∅*=∈*=∈ . peace

suppose L= {} this language means two things either there is no final state or final state is unreachable from initial state .

And for L={∈} this language means without any input we can reach the final state ,So ∅ and ∈ is very much different . But in this case ∅*=∈*=∈ . peace

+21 votes

**B** is only correct

why not A?

A's RHS can accept null strings, LHS can't.

if $r=ab$ then $r^*=abababa$.....

$r(^*)=ab(^*)=ab$

0 votes

+1

Sir,

A is not true as

r (*) cant accpt null string, the precedence is for () first, means it will be on an empty string rather than r

Whereas r* accepts null string

But i am nit getting how C is not true ?

I mean (r+s)* accepts all strings as r*+s* . Doesnt it ?

A is not true as

r (*) cant accpt null string, the precedence is for () first, means it will be on an empty string rather than r

Whereas r* accepts null string

But i am nit getting how C is not true ?

I mean (r+s)* accepts all strings as r*+s* . Doesnt it ?

0 votes

People who are confused what's going on in this question please refer this

Option A is wrong as right hand side can produce null string while left hand side cannot.

Now coming to answer B , there can be 2 situation with this

1. Mistake in presenting option B

Option given there is wrong as (r*s*) cannot generate rsr

2. Answer will be correct if we have (r*s*)* =(r+s)* you can refer Ullman section 3.4.6

3. If we think like this option B can be correct

(r*s*)=(r+s)*

Taking closure on both the sides we get

(r*s*)*=((r+s)*)*

We know thst (a*)*= a* check identities

Hence (r*s*)*= (r+s)*

Others please check if my third interpretation is valid and correct me if I am wrong .

52,345 questions

60,470 answers

201,795 comments

95,272 users