2.5k views

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only.

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

edited | 2.5k views
+12
L(r) = $1(1+0)^*$
L(s) = $1^+0$
L(t) = $1^*0$

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 \dots$. 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
0
Both 's' and 't' looks same..
+2
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
0

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