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$ @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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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