# Is a language that sits between two regular languages also regular?

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.

Suppose

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

• 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? – Apass.Jack Feb 4 at 20:27

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