C is correct

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

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

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

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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 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?

- $S \subset T$
- $T \subset S$
- $S = T$
- $S \cap T = \phi$

+24 votes

+1

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.

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

+4 votes

0

Bt string abbbabbb is not accepted by T which is accepted by S...then how S=T?Please correct me if I m wrong...

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,704 questions

46,749 answers

140,537 comments

58,314 users