0
$\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 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

$\endgroup$
  • 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$ – Apass.Jack Feb 4 at 20:27
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.