Suppose that L0, L1, L2 are languages over the same alphabet and that

L0 ⊆ L1 ⊆ L2.

Is it true that if L0 and L2 are regular, then L1 must be regular as well?

By regular = the set of words accepted by a finite automaton.


L0 = { $a^{\textrm{n}}$ | n = 2}

L2 = { $a^{\textrm{n}}$ | n => 0}

how can i find a set for L1 that is NOT Regular when there are no parameters or syntax on what the machine accepts or not?

I'm thinking

L1 = { $a^{\textrm{n}}$ | n = prime number }

but I'm not sure how to start proving it

  • 1
    $\begingroup$ Although your $L0, L1, L2$ is a triple of valid counterexample, can you find simpler ones? Do you know one language that is not regular? $\endgroup$
    – John L.
    Feb 4, 2019 at 20:27

2 Answers 2


The answer is no. Here's a counterexample.

$$Nothing = \varnothing$$

$$Something = \{ 0^n 1^n \mid n \in \mathbb{N} \}$$

$$Everything = \Sigma^*$$

Now, both $Nothing$ and $Everything$ are regular, because they can be described by regular expressions. And we know that $Nothing \subseteq Something \subseteq Everything$. But $Something$ is a classic example of a language that is not regular.


Any time you're asked questions like "Is a subset of a regular language always regular?" or "Is a superset of a regular language always regular?", you have the best chance if you pick the biggest possible language to take subsets of, and the smallest possible language to take supersets of. Thankfully, the biggest possible and smallest possible languages are both regular.


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.