edited by
11,369 views
28 votes
28 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$
edited by

5 Answers

Best answer
33 votes
33 votes

Correct Option: C

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

edited by
9 votes
9 votes
C is correct

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

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

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 .

0 votes
0 votes
answer is C
Answer:

Related questions

40 votes
40 votes
4 answers
1
Kathleen asked Sep 14, 2014
10,292 views
Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$.Which of the following is TRUE?$L = 0^+$$L$ is regular but not $0^+$$L$ is context free but not ...
41 votes
41 votes
6 answers
4
Kathleen asked Sep 14, 2014
11,866 views
Which of the following need not necessarily be saved on a context switch between processes?General purpose registersTranslation look-aside bufferProgram counterAll of the...