How can this be? I don't think it is actually possible for a non-regular language to be a subset of a regular language. What examples are there where this is true?
$\begingroup$
$\endgroup$
-
$\begingroup$ @Choirbean What context do you think might be required? $\endgroup$ – David Richerby May 8 '17 at 21:56
-
$\begingroup$ In fact, any infinite (regular) language has a non-regular subset. This can be obtained by forcing "growing gaps" between the length the strings in the chosen subset. $\endgroup$ – Hendrik Jan May 8 '17 at 22:03
-
$\begingroup$ Don't we have like a dozen duplicates of this? $\endgroup$ – Raphael♦ May 8 '17 at 22:32
-
1$\begingroup$ @Raphael The right column is always helpful: Show that every infinite language has a non-regular subset. $\endgroup$ – Hendrik Jan May 9 '17 at 0:12
$\begingroup$
$\endgroup$
Every language over an alphabet $\Sigma$ is, by definition, a subset of $\Sigma^*$, which is regular. If you want a less trivial example,
$$\{a^nb^n\mid n\geq 0\}\subseteq L(a^*b^*)\,.$$
answered May 8 '17 at 21:56
