in Theory of Computation edited by
7,962 views
34 votes

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

  1. $r^{(^\ast)} =r^\ast$
  2. $(r^\ast s^\ast)=(r+s)^\ast$
  3. $(r+s)^\ast = r^\ast + s^\ast$
  4. $r^\ast s^\ast = r^\ast+s^\ast$
in Theory of Computation edited by
8k views

14 Comments

Anser is given as B only . I think A is also True . Correct me if wrong
0
A's RHS can accept null strings, LHS can't.
if r=ab then r*=abababa.....
r(*)=ab(*)=ab
12

why option a is not correct ?

@srestha

0

r(*) = r*

and

r(*)=r*

pls tell the difference between above two

5
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
4

if r=a(a*)

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

0
a(a*) and a(a*)(*) same
but similarly (a+b)* and (a*b*)* are both similar
those are not contradictory
1

got it.if

r(*) = r* this is the case then both are same

confirm this too pls

0
does a(*) means a.(fi*)..ie - a ??
0
@PEKKA how b is correct..?

R1= (r*s*)*  !=   R2=(r+s)*  

In R1 "sr" can never be generated but in R2 " sr " can be generated
2
how can we get "sr " using lhs of option B?

please @arjunsir through some light
0
(r*s*)* = (r*s*)(r*s*) = (s)(r)
5
thanks a lot got it
0

How $\left ( r^{*}s^{*} \right )^{*}$ = $\left ( r + s \right )^{*}$ ? Any proof in simple words !!

0

Subscribe to GO Classes for GATE CSE 2022

7 Answers

50 votes
 
Best answer
  1. Is the answer
  2. RHS generates $\Sigma^*$ while LHS can't generate strings where $r$ comes after $s$ like $sr, srr$ etc. LHS $\subset$ RHS.
  3. LHS generates $\Sigma^*$ while RHS can't generate strings where $r$ comes after an $s$. RHS $\subset$ LHS.
  4. 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.
edited by
by

8 Comments

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

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

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

11
^But why you took {}* and not $\epsilon^*$ ? That seems more appropriate. $\epsilon^* = \epsilon$, so answer would still be same.
3
edited by
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
3
Option B has to be right option because,

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

 Thus it can produce Σ*

And obviously (r*s*)* can also produce Σ*

================

For those saying strings starting with s can't be produced:

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

== s(r+s)*
0
can anyone explain the difference between the LHS and RHS of option A… I did not get the difference
0
23 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$

edited by

7 Comments

r(*) =ab(*) =ab

Is this the only string possible in LHS?

Or abababa...  Also possible?

What does it exactly mean (*)...?

@Amitabh Tiwari 1

@Anirudh
1
What does it exactly mean by (*)...?
3
Please clear above doubt
0
A is not correct got it but how  B is correct ??

(P* q*)* = (P* + q*)* Then how B option is correct ??
0
someone please clarify what does (*) mean?
1

Wrong answer.   LHS can't generate strings where r comes after s like sr. where RHS can generate any combination of r and s.  LHS $\subset$ RHS . B,C,D are FALSE for sure.

0
a write ans bro
0
4 votes

Only option B is Correct.

2 Comments

There is no *  outside LHS of option B. 

0

Wrong answer. Please check option B.

0
1 vote

ANS: A.

B) LHS: (r*s*)*={ε ,r,s,rs....}

RHS:(r+s)*={ε ,r,s,rs,sr...} ,sr can't be generated by LHS...so wrong.

C)(r+s)* - generates all string over {r,s}

(r*+s*) can't generate anything as combination of sr, so wrong.

D) r*s*= {ε ,r,s,rs..} but r*+s* cannot generate rs , so wrong.

by

1 comment

 

Caption

 

 

 

0
0 votes
Option B is only true .

4 Comments

how???
0
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 ?
1

 Abbas2131

 (r+s)*  accept rs but 

r*+s* cant

0

@Abbas2131

(r+s)* means any string of a,b

r* + s* means any string of any length of either 'r' or 's'

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

@Arjun, @Sreshta

1 comment

can u please tell me what's the difference between LHS & RHS in option A ???

about point 3 of your answer - 

can we do like that. I mean here * is considered as an operator(kleen closure), not a constant. I'm not sure about it, but may be.....

 

0
0 votes
A) Answer.
(B) RHS generates Σ* while LHS can't generate strings where r comes after s like sr, srr, etc.
LHS ⊂ RHS.
(C) LHS generates Σ* while RHS can't generate strings where r comes after an s.
RHS ⊂ 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 ⊂ LHS.

1 comment

Please don’t copy other's answers if you have nothing to add.
0
Answer:

Related questions