Theory of Computation (Regular/Non-Regular proof)

Question

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 alphabet is accepted by the machine

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 don't know how to prove it.

Answer 1

I think this is classical for Pumping Lemma.

Suppose $L_1$ is regular, then there exists integer $p$ and a long enough string $w=a^k$ that could be written as $$w = xyz, \lvert xy \rvert \leq p, \lvert y \rvert \geq 1,$$ such that $xy^nz \in L_1$ for every $n$.

Take $n = \lvert xz \rvert$, then $\lvert xz \rvert$ divides $\lvert xy^nz \rvert$. Which contradicts the definition of $L_1$.

Answer 2

Here's an example where it may be easier to see:

$L_0$ = { $ab$ }, $L_1$ = { $a^nb^n$ | $n > 0$ }, $L_2$ = { $a^+b^+$ }

Answer 3

The existence of a non-regular language between the languages $L_0=\{aa\}$ and $L_2=a^*$ can also be proved without the pumping lemma. There are only countably many regular expressions over the alphabet $\{a\}$, because each of these regular expressions is a word in the alphabet $\{ ),(,+,\cdot,^*,\emptyset,a\}$. On the other hand, there are uncountably many languages between $L_0$ and $L_2$ (because there are uncountably many subsets of $\mathbb{N}$ and each such subset $K$ yields a language $L_1=L_0 \cup \{a^{i+3} \mid i \in K\}$).

This proves that there exists a non-regular language $L_1$ between $L_0$ and $L_2$, but does not provide any particular language $L_1$.