Register

GATE CSE 1992 | Question: 02,xvii

• edited by
14,501 views
42 votes
42 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$
• edited by
User Avatar

8 Answers

0 votes
0 votes
Option B is only true .
User Avatar
0 votes
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

User Avatar
0 votes
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.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

28 votes
28 votes
1 answer
1
Kathleen asked Sep 13, 2014
7,448 views
GATE CSE 1992 | Question: 02,xx
In which of the cases stated below is the following statement true? "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language". $M_{1}$ ... $M_{1}$ and $M_2$, the above statement true.
In which of the cases stated below is the following statement true?"For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ r...
User Avatar
24 votes
24 votes
4 answers
2
Kathleen asked Sep 13, 2014
10,845 views
GATE CSE 1992 | Question: 02,xvi
Which of the following is/are a tautology? $a \vee b \to b \wedge c$ $a \wedge b \to b \vee c$ $a \vee b \to \left(b \to c \right)$ $a \to b \to \left(b \to c \right)$
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$
User Avatar
18 votes
18 votes
2 answers
3
Kathleen asked Sep 13, 2014
1,786 views
GATE CSE 1992 | Question: 02-xii
Which of the following is an example of a spooled device? The terminal used to input data for a program being executed. The secondary memory device in a virtual memory system A line printer used to print the output of a number of jobs. None of the above
Which of the following is an example of a spooled device?The terminal used to input data for a program being executed.The secondary memory device in a virtual memory syst...
User Avatar
9 votes
9 votes
2 answers
4
Kathleen asked Sep 12, 2014
3,002 views
GATE CSE 1992 | Question: 02,v
Start and stop bits do not contain any 'information' but are used in serial communication Error detection Error correction Synchronization Slowing down the communications
Start and stop bits do not contain any 'information' but are used in serial communicationError detectionError correctionSynchronizationSlowing down the communications
User Avatar
Link Copied!