The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes
Which of the following regular expression identities are true?

(A) r(*) = r*

(B) (r*S*)* = (r + s)*

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

(D) r*s* = r* + s*
asked in Theory of Computation by Loyal (2.6k points)
edited by | 1k views
Anser is given as B only . I think A is also True . Correct me if wrong
A's RHS can accept null strings, LHS can't.
if r=ab then r*=abababa.....

why option a is not correct ?


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


if r=a(a*)

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

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

got it.if

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

confirm this too pls

does a(*) means a.(fi*) - a ??
@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
how can we get "sr " using lhs of option B?

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

2 Answers

+13 votes
Best answer
B is only correct

why not A?

A's RHS can accept null strings, LHS can't.
if r=ab then r*=abababa.....
answered by Loyal (2.8k points)
selected by
r(*) =ab(*) =ab

Is this the only string possible in LHS?

Or abababa...  Also possible?

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

@Amitabh Tiwari 1

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

(P* q*)* = (P* + q*)* Then how B option is correct ??
someone please clarify what does (*) mean?
0 votes
Option B is only true .
answered by Junior (637 points)

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 ?


 (r+s)*  accept rs but 

r*+s* cant


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,713 questions
40,262 answers
38,894 users