GATE CS 1991 Q03 — Regular Expressions and Finite Automata

Let us analyze the languages generated by the three regular expressions:

• $L(r) = L(1(1+0)^*)$: The set of all strings over $\{0, 1\}$ that start with the symbol $1$.
• $L(s) = L(11^*0)$: The set of strings consisting of one or more $1$s followed by exactly one $0$ (i.e., $1^+0$).
• $L(t) = L(1^*0)$: The set of strings consisting of zero or more $1$s followed by exactly one $0$.

Now, let us check the subset relations:

1. $L(s) \subseteq L(r)$: Every string in $L(s)$ starts with at least one $1$, so it must belong to $L(r)$ (which contains all strings starting with $1$). Hence, $L(s) \subseteq L(r)$ is true.
2. $L(s) \subseteq L(t)$: Since $1^+0 \subseteq 1^*0$, every string in $L(s)$ is also in $L(t)$. Hence, $L(s) \subseteq L(t)$ is true.

Since both conditions hold, both options A and C (which are logically identical) are correct.