If $L_{1} \subseteq L_{2}$ and $ L_{2}$ is regular, does it follow that $L_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we make?

  • 5
    $\begingroup$ Please do not vandalize your question. $\endgroup$
    – ArtOfCode
    Aug 10 '16 at 12:49

No, $L_1$ is not necessarily regular. We could have $L_2 = \Sigma^*$, in which case $L_1$ could be anything at all.


Not the answer you're looking for? Browse other questions tagged or ask your own question.