0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ @Choirbean What context do you think might be required? $\endgroup$ Commented May 8, 2017 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$ Commented May 8, 2017 at 22:03
  • $\begingroup$ Don't we have like a dozen duplicates of this? $\endgroup$
    – Raphael
    Commented May 8, 2017 at 22:32
  • 1
    $\begingroup$ @Raphael The right column is always helpful: Show that every infinite language has a non-regular subset. $\endgroup$ Commented May 9, 2017 at 0:12

1 Answer 1

5
$\begingroup$

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^*)\,.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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