1
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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?

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

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

$\endgroup$
9
  • $\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
    Sep 4, 2022 at 19:20
  • $\begingroup$ $L\cup \{u\}$ is a superset of $L$ that is different of $L$. $\endgroup$
    – Nathaniel
    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
    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
    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
    Sep 21, 2022 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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