in Theory of Computation edited by
9,442 views
25 votes
25 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
9.4k views

4 Comments

Typo. Comma {a,b}
0
0
Where?
0
0
edited
0
0

4 Answers

32 votes
32 votes
Best answer

Correct Option: C

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

edited by
by

4 Comments

Both $S$ and $T$ can generate all strings over $\Sigma$ so their intersection is also = all strings over $\Sigma$  (not $\phi$)
2
2
Okay got it
0
0
If option A would have been SāŠ† T then it would be an ambiguous question.
1
1
9 votes
9 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
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
3
Ohh...now I understand Thank You
0
0
0 votes
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
0
0 votes
0 votes

Option C,

S = T,

All the below forms of REX are equivalent,

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

Answer:

Related questions