in Theory of Computation edited by
7,764 views
21 votes

Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true?

  1. $S \subset T$
  2. $T \subset S$
  3. $S = T$
  4. $S \cap T = \phi$
in Theory of Computation edited by
7.8k views

6 Comments

C is correct

S=(a+b*)*=(a*(b*)*)*=(a*b*)*

T=(a+b)*=(a*b*)*     so S=T
9
can anyone explain option D?
1
If two sets are equal then how intersection can be null??

A={1,2,3} B ={1,2,3} so when A=B then their intersection can't be null.
0

Some of the regular expression equivalent to (a+b)*  which might help

(a+b)* =(a*+b*)* = (a*b*)* = (a*+b)* =(a+b*)* =a*(ba*)* =b*(ab*)*

0
Typo. Comma {a,b}
0

Subscribe to GO Classes for GATE CSE 2022

3 Answers

30 votes
 
Best answer

Correct Option: C

$S=T$. Both generates all strings over $\Sigma$.

edited by
by

6 Comments

Can anyone explain in more detail? I am confused that regular expression S will generate more number of b's as compared to expression T. If they need to be equal they both should always generate same set of symbol but number of b's generated by expression S can be more.

Is this solution is an identity of regular expression? or we need to evaluate set of string and make the comparison.
1

vupadhayay

see the above comment both are equal

0
option C is ok but what about option D?
0
Both $S$ and $T$ can generate all strings over $\Sigma$ so their intersection is also = all strings over $\Sigma$  (not $\phi$)
2
Okay got it
0
If option A would have been S⊆ T then it would be an ambiguous question.
1
8 votes
C is correct

S=(a+b*)*=(a*(b*)*)*=(a*b*)*

T=(a+b)*=(a*b*)*     so S=T

3 Comments

Bt string abbbabbb is not accepted by T which is accepted by S...then how S=T?Please correct me if I m wrong...
0
T = (a+b)*  this language is set of all possible strings it will have all strings belongs to alphabet  Σ={a.b}

(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)

now take a from first(a+b) then b from second(a+b)and so on... in this way ur string will be accepted by T..
3
Ohh...now I understand Thank You
0
0 votes
answer is C

1 comment

Can we use regular expression identities over alphabet a and b?

Here P and Q are regular expression

(P+Q)*=(P*+Q)*

P+Q=Q+P

So, (P+Q)*=(Q+P)*=(Q+P*)*

Also , from regular expression identities.I'm unable to obtain (P+Q*)*
0
Answer:

Related questions