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$

Question

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:

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$). — Nathaniel, Commented Sep 4, 2022 at 17:01
Also what's the purpose of $L_2$? You can always choose $L_2 = \{0,1\}^*$. — Steven, Commented 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. — tomato, Commented Sep 4, 2022 at 17:07
@Steven $L_2$ is supposed to be not regular, so you can't choose $L_2 = \{0, 1\}^*$. — Nathaniel, Commented Sep 4, 2022 at 17:35
@Nathaniel, oh I see. That restriction is only mentioned in the title, so I missed it. — Steven, Commented Sep 4, 2022 at 17:39

D.W. · Accepted Answer · 2022-09-04 17:06:49Z

1

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?

answered Sep 4, 2022 at 17:06

D.W.♦

166k21 gold badges230 silver badges490 bronze badges

$\begingroup$ How do we define $L_2$ then? Since $L \subseteq L_2$ and $L_2 \neq L$ $\endgroup$
– tomato
Commented Sep 4, 2022 at 17:10
$\begingroup$ 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? $\endgroup$
– tomato
Commented Sep 4, 2022 at 17:16
$\begingroup$ 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\}$? $\endgroup$
– tomato
Commented Sep 4, 2022 at 17:39

Add a comment |

Nathaniel · Accepted Answer · 2022-09-04 17:52:21Z

1

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\}$?

answered Sep 4, 2022 at 17:52

Nathaniel

17k2 gold badges30 silver badges55 bronze badges

$\begingroup$ 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. $\endgroup$
– tomato
Commented Sep 4, 2022 at 19:20
$\begingroup$ $L\cup \{u\}$ is a superset of $L$ that is different of $L$. $\endgroup$
– Nathaniel
Commented Sep 4, 2022 at 19:53
$\begingroup$ 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? $\endgroup$
– tomato
Commented Sep 4, 2022 at 20:23
$\begingroup$ I already hinted that $L_1 = \emptyset$ is enough. Also, you would need to prove that $L_2$ is CFL and not regular. $\endgroup$
– Nathaniel
Commented Sep 4, 2022 at 21:22
1

$\begingroup$ "can we suppose $L$ is CFL and not regular without proof?" > are you serious? That's litteraly you hypotheses in the question… $\endgroup$
– Nathaniel
Commented Sep 21, 2022 at 16:05

| Show 4 more comments

2 Answers 2