The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

02. 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?

(a) $r^{(^*)} =r^*$

(b) $(r^*s^*)=(r+s)^*$

(c) $(r+s)^* = r^* + s^*$

(d) $r^*s^* = r^*+s^*$

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

(a) $r^{(^*)} =r^*$

(b) $(r^*s^*)=(r+s)^*$

(c) $(r+s)^* = r^* + s^*$

(d) $r^*s^* = r^*+s^*$

+25 votes

Best answer

(a) is the answer

(b) RHS generates $\Sigma^*$ while LHS can't generate strings where $r$ comes after $s$ like $sr, srr$ etc. LHS $\subset$ RHS.

(c) LHS generates $\Sigma^*$ while RHS can't generate strings where $r$ comes after an $s$. RHS $\subset$ LHS.

(d) 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.

(b) RHS generates $\Sigma^*$ while LHS can't generate strings where $r$ comes after $s$ like $sr, srr$ etc. LHS $\subset$ RHS.

(c) LHS generates $\Sigma^*$ while RHS can't generate strings where $r$ comes after an $s$. RHS $\subset$ LHS.

(d) 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.

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

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

@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.

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

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

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

@Amitabh Tiwari 1 @Arjun Sir, here in this question mentioned in link https://gateoverflow.in/83956/gate-1992-which-following-regular-expression-identities-true

r(*)=r* is false, but in this question it's true. So, what is it True or False?

In this question , it is r^{(*)}=r* and in your given link r(*)=r*

moreover , here option B) is (r*S*) = (r + s)* .. there option B) is (r*S*)* = (r + s)* ..

as you know (r*S*) != (r + s)* and other options also false so option A is chosen here.

These 2 questions are Not same ..option B is different

see this is 1992 paper, #xvii see here

and option A) here r^{(*)} = r

option B, C and D all are false here .

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,713 questions

40,262 answers

114,373 comments

38,894 users