The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
783 views

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?

  1. $r^{(^*)} =r^*$
  2. $(r^*s^*)=(r+s)^*$
  3. $(r+s)^* = r^* + s^*$
  4. $r^*s^* = r^*+s^*$
asked in Theory of Computation by Veteran (59.4k points)
edited by | 783 views
+5

r(*) = r*

and

r(*)=r*

pls tell the difference between above two

2 Answers

+27 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.
answered by Veteran (339k points)
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

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

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

 

+2
^But why you took {}* and not $\epsilon^*$ ? That seems more appropriate. $\epsilon^* = \epsilon$, so answer would be still same.
+1
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
+1

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

+1

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.

+1

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 .

0
@Bikram, makes sense, Sir! Thanks.
0
a is partially correct i think..
0

https://gateoverflow.in/83956/gate-1992-2-xii As per this question option 1 is false. Please clarify.

–1 vote
B, C, D are wrong so,answer must be A.
answered by Active (1.4k points)


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

34,780 questions
41,758 answers
118,934 comments
41,400 users