in Theory of Computation edited by
5,180 views
24 votes

Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0 $ be three regular expressions. Which one of the following is true?

  1. $L(s) \subseteq L(r)$ and $L(s) \subseteq L(t)$

  2. $L(r) \subseteq L(s)$ and $L(s) \subseteq L(t)$

  3. $L(s) \subseteq L(t)$ and $L(s) \subseteq L(r)$

  4. $L(t) \subseteq L(s)$ and $L(s) \subseteq L(r)$

  5. None of the above

in Theory of Computation edited by
5.2k views

1 comment

L(r) = $1(1+0)^*$
L(s) = $1^+0$
L(t) = $1^*0$
(A) and (C) are answer!
15

Subscribe to GO Classes for GATE CSE 2022

5 Answers

37 votes
 
Best answer

Answer is A and C.

To know the answer let us check all the options:

  1. $L(s)\subseteq L(r)$:  strings generated by $s$ are any numbers of $1$'s followed by one $0$, i.e., $10,110,1110,1110,\dots$. Strings generated by $r$ are is $1$ followed by any combination of $0$ or $1$, i.e., $1,10,11,1110,101,110 \ldots$. This shows that all the strings that can be generated by $s$, can also be generated by $r$ it means $L(s)\subseteq L(r)$ is true.
    $L(s)\subseteq L(t)$: here strings generated by $t$ are any numbers of $1$ (here $1^*$ means we have strings as $\epsilon,1,11,111,\dots$) followed by only one $0$, i.e., $0,10,110,1110, \dots$. So we can see that all the strings that are present in $s$ can also be generated by $t$, hence $L(s) \subseteq L(t)$ which shows that option A is true.
     
  2. $L(r)\subseteq L(s)$: this is false because string $1$ which can be generated by $r$, cannot be generated by $s$.
     
  3. Same as option A.
     
  4.  $L(t) \subseteq L(s)$: this is false because string $0$ which can be generated by $t$,cannot be generated by $s$.
edited by

4 Comments

Both 's' and 't' looks same..
0
t can generate only zero while S cannot thus T is superset of S and not subet .Thus only c is correct.

 it should be strictly subset in the all cases above.

please correct if i am wrog? @ArjunSir
2

@ankyAS Options A and C are same so how only C can be the answer? 

 

0

L(r) $\supseteq  L(t) \supseteq$ L(s) .

0
8 votes
If we take simpler strings,

t accepts 0, s doesn't. But both accept 10. So s is a subset of t.

r accepts 1, s doesn't. But both accept 10. So, s is a subset of r.

So, options A and C, as both are the same.
3 votes
option A and C are the same and are the answers as well.
0 votes
L(s) ⊆ L(r), because 'r' generates all strings which 's' does but 'r' also generates '101' which 's' does not generate.
L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.
0 votes

L(r) = 1(1+0)* = {1,10,11,100,101,110,111, …..}

L(s) = $1^{+}$0 = {10,110,1110, ….}

L(t) = $1^{*}$0 = {0, 10,110,1110, ….}

From the above langages we can can write

L(s) ${\displaystyle \subset }$ L(t) ${\displaystyle \subset }$ L(r) 

Therefore  L(s) ${\displaystyle \subset }$  L(r)  and  L(s) ${\displaystyle \subset }$  L(t)  but not  L(s) ${\displaystyle \subseteq }$  L(r)  and  L(s) ${\displaystyle \subseteq }$  L(t)

Therefore the answer should be

E)None of the above

Correct me if i am wrong

reshown by
Answer:

Related questions