# Theory of Computation (Regular/Non-Regular proof)

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.

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

• So i guess there's no other way to prove it aside from pumping lemma?
– Ken
Feb 4 '19 at 20:12

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^+$$ }

• What does this say though?
– Ken
Feb 4 '19 at 20:13
• I mean what's the point of this?
– Ken
Feb 4 '19 at 20:13
• $L_1$ is shown in Wikipedia as not Regular! Feb 4 '19 at 20:23