GATE CSE 2000 | Question: 1.4

Question

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?

• A. $S \subset T$
• B. $T \subset S$
• C. $S = T$
• D. $S \cap T = \phi$

Comments

Where?

---

edited

---

both are (a+b)* and hence they are equal and they are subset of each other but NOT PROPER SUBSET.

Answer 1

Correct Option: C

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

Comments

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.

Answer 2

C is correct

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

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

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...

---

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

Answer 3

Here in this question  s= (a + b*)*   when we open it  it will become {  ε,  a, b, a^2, a^3, .., b^2, b^3,.. ab, abb... }*  And we know that   to make it sigma* we need only (a+ b)* this deadly combo to generate all this strings so ultimately it will become sigma * .
And given T is automatically in this form (a + b)* so it  is also a sigma*  that's why both are equal .

Answer 4

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 5

answer is C

Comments

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

Answer 6

use this formula: (a*b*)* = (a+b)* so convert both expressions like this form and you have to use this formula too (b*)* = b* thus both are equal.