Redirected
edited by
14,297 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

8 Answers

Best answer
56 votes
56 votes
  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
25 votes
25 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 votes
7 votes

Only option B is Correct.

1 votes
1 votes

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.

Answer:

Related questions

28 votes
28 votes
1 answer
1
24 votes
24 votes
4 answers
2
Kathleen asked Sep 13, 2014
9,936 views
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)$
18 votes
18 votes
2 answers
3
9 votes
9 votes
2 answers
4
Kathleen asked Sep 12, 2014
2,962 views
Start and stop bits do not contain any 'information' but are used in serial communicationError detectionError correctionSynchronizationSlowing down the communications