Skip to main content
3 of 4
added 38 characters in body

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$, exists $L_1,L_2\subseteq\{0,1\}^*$ with:

  • $L_1$ is $REG$
  • $L_2$ is $CFL$ and not $REG$
  • $L_1 \subseteq L_2 $
  • $L \subseteq L_2 $ and $L \neq L_2$

I struggle at showing it for all $L$.

What I did so far is some kind of a little sketch.

Let $L_1 = L(01)$ and $L_2 = \{0^n1^n | n \geq 0\}$ then $L_1$ is obviously $REG$ and $L_2$ is obviously $CFL$ and not $REG$

Also $L_1 \subseteq L_2$ and $L \subseteq L_2$ and $L_2 \neq L$

But how do I proceed from here? How do I show it for every $L$?