# 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$$?

• What is the purpose of $L_1$? You could always pick $L_1 = \emptyset$ (it is always regular and a subset of $L_2$). Sep 4, 2022 at 17:01
• Also what's the purpose of $L_2$? You can always choose $L_2 = \{0,1\}^*$. Sep 4, 2022 at 17:06
• I actually don't know. That was a question from a test and I still try to find a solution for this question. Sep 4, 2022 at 17:07
• @Steven $L_2$ is supposed to be not regular, so you can't choose $L_2 = \{0, 1\}^*$. Sep 4, 2022 at 17:35
• @Nathaniel, oh I see. That restriction is only mentioned in the title, so I missed it. Sep 4, 2022 at 17:39

Your approach is not going to work. If $$L=\{00\}$$ (say) then you will not have $$L \subseteq L_2$$.

Hint for a better approach: Could $$L$$ be $$\{0,1\}^*$$? Why or why not?

• How do we define $L_2$ then? Since $L \subseteq L_2$ and $L_2 \neq L$ Sep 4, 2022 at 17:10
• If we would set $L_2 = \{0,1\}^*$ and $L_1 = \emptyset$ then it would be valid for every $L \subseteq L_2$ right? Would this be a possible solution or still to imprecise? Sep 4, 2022 at 17:16
• Ah, I forgot that $L_2$ and $L$ are not regular. I think that's the main problem I have. How do I proceed without using a specific example for a CFL language like $\{0^n1^n\}$? Sep 4, 2022 at 17:39

Since $$L$$ is not regular it is different than $$\Sigma^*$$. What would happen if you choose a word $$u\notin L$$ and consider $$L\cup \{u\}$$?

• I don't really know where to go with this. Can you drop a another hint? I'm still confused because L needs to be a subset of L2 while simultaneously L != L2. So L2 has to be superset of L. Sep 4, 2022 at 19:20
• $L\cup \{u\}$ is a superset of $L$ that is different of $L$. Sep 4, 2022 at 19:53
• Ah right. So $L \cup \{u\}$ can be used as $L_2$. That way we satisfy $L \subseteq L_2$ and $L \neq L_2$. And $L_1 \subseteq L_2$ is obvious because $L_1$ could be something simple like some arbitrary $w \in L_2$. Am I missing something? Sep 4, 2022 at 20:23
• I already hinted that $L_1 = \emptyset$ is enough. Also, you would need to prove that $L_2$ is CFL and not regular. Sep 4, 2022 at 21:22
• "can we suppose $L$ is CFL and not regular without proof?" > are you serious? That's litteraly you hypotheses in the question… Sep 21, 2022 at 16:05