33 votes 33 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? $L(s) \subseteq L(r)$ and $L(s) \subseteq L(t)$ $L(r) \subseteq L(s)$ and $L(s) \subseteq L(t)$ $L(s) \subseteq L(t)$ and $L(s) \subseteq L(r)$ $L(t) \subseteq L(s)$ and $L(s) \subseteq L(r)$ None of the above Theory of Computation gate1991 theory-of-computation regular-expression normal multiple-selects + – Kathleen asked Sep 12, 2014 • edited Apr 17, 2021 by Lakshman Bhaiya Kathleen 11.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Manu Thakur commented Nov 29, 2017 reply Follow Share L(r) = $1(1+0)^*$ L(s) = $1^+0$ L(t) = $1^*0$ (A) and (C) are answer! 15 votes 15 votes Ajitgate21 commented Oct 20, 2022 reply Follow Share R=1(1+0)*. L=1{e,0,1,01,10,00,11,...}=> L={1,10,11,101,110,100,111,..}. S=11*0. L=1{e,1,11,111,1111,..}0 => L={1,11,111,111,1111,..}0. L={10,110,1110,11110, ...}. T=1*0. L={e,1,11,111,1111,..}0. => L={0,10,110,1110,11110,….}. Now see, S is subset of T, and S and T Both are subset of R. 0 votes 0 votes Please log in or register to add a comment.
Best answer 43 votes 43 votes Answer is A and C. To know the answer let us check all the options: $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. $L(r)\subseteq L(s)$: this is false because string $1$ which can be generated by $r$, cannot be generated by $s$. Same as option A. $L(t) \subseteq L(s)$: this is false because string $0$ which can be generated by $t$,cannot be generated by $s$. neha pawar answered Oct 14, 2014 • edited Apr 17, 2021 by Lakshman Bhaiya neha pawar comment Share Follow See all 4 Comments See all 4 4 Comments reply Aditya commented Jul 27, 2015 reply Follow Share Both 's' and 't' looks same.. 0 votes 0 votes ankyAS commented Dec 6, 2016 reply Follow Share 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 votes 2 votes Harshada commented Dec 24, 2018 reply Follow Share @ankyAS Options A and C are same so how only C can be the answer? 0 votes 0 votes raja11sep commented Jul 14, 2021 i edited by JAINchiNMay Nov 16, 2022 reply Follow Share $ L(r) \supseteq L(t) \supseteq L(s) $. 0 votes 0 votes Please log in or register to add a comment.
11 votes 11 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. Bidyudipta Chanda answered Mar 16, 2017 Bidyudipta Chanda comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes option A and C are the same and are the answers as well. Gate Keeda answered Oct 14, 2014 Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 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. varunrajarathnam answered Aug 20, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.