The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
950 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$
asked in Theory of Computation by Veteran (59.4k points)
edited by | 950 views
+1
C is correct

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

T=(a+b)*=(a*b*)*     so S=T
0
can anyone explain option D?

3 Answers

+24 votes
Best answer

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

answered by Veteran (339k points)
edited by
0
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.
0

vupadhayay

see the above comment both are equal

+4 votes
C is correct

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

T=(a+b)*=(a*b*)*     so S=T
answered by Active (3.4k points)
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...
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..
0
Ohh...now I understand Thank You
0 votes
answer is C
answered by (189 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,943 questions
41,958 answers
119,194 comments
41,472 users