9,442 views

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$

Typo. Comma {a,b}
Where?
edited

Correct Option: C

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

by

Both $S$ and $T$ can generate all strings over $\Sigma$ so their intersection is also = all strings over $\Sigma$  (not $\phi$)
Okay got it
If option A would have been Sā T then it would be an ambiguous question.
C is correct

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

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

Bt string abbbabbb is not accepted by T which is accepted by S...then how S=T?Please correct me if I m wrong...
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..
Ohh...now I understand Thank You

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

Option C,

S = T,

All the below forms of REX are equivalent,

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