858 views

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?

1. $r^{(^*)} =r^*$
2. $(r^*s^*)=(r+s)^*$
3. $(r+s)^* = r^* + s^*$
4. $r^*s^* = r^*+s^*$
edited | 858 views
0
Anser is given as B only . I think A is also True . Correct me if wrong
+7
A's RHS can accept null strings, LHS can't.
if r=ab then r*=abababa.....
r(*)=ab(*)=ab
0

why option a is not correct ?

+5

r(*) = r*

and

r(*)=r*

pls tell the difference between above two

+2
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
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
0

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 ??
+1
@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
0
how can we get "sr " using lhs of option B?

+2
(r*s*)* = (r*s*)(r*s*) = (s)(r)
0
thanks a lot got it

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
0

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

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.
+4

**** Disclaimer : I am not sure that its right or wrong . So if its wrong please dont 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

+2
^But why you took {}* and not $\epsilon^*$ ? That seems more appropriate. $\epsilon^* = \epsilon$, so answer would still be same.
+1
yes answer might be same but i think ( for safety purpose i say " i think " what if i got wrong :D ) its 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

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
+1
r(*) =ab(*) =ab

Is this the only string possible in LHS?

Or abababa...  Also possible?

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

@Amitabh Tiwari 1

@Anirudh
+3
What does it exactly mean by (*)...?
0
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?
Option B is only true .
0
how???
+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 ?
0

(r+s)*  accept rs but

r*+s* cant

–1 vote
B, C, D are wrong so,answer must be A.