1
$\begingroup$
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.

$\endgroup$
1
$\begingroup$

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

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

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

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

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.