Timeline for 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$
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2022 at 16:05 | comment | added | Nathaniel | "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 13:21 | comment | added | tomato | Somehow the hint didn't help me, but can we suppose L is CFL and not regular without proof? If so, because $L_2 \cup \{u\}$ with $u \notin L$, then $L_2$ would also be CFL and not regular because the union just adds one word and not a whole language? | |
| Sep 20, 2022 at 10:57 | comment | added | Nathaniel | Hint: regular languages are closed under set difference and $L$ is a not regular CFL. | |
| Sep 20, 2022 at 10:52 | comment | added | tomato | I still haven't found a way to show that $L_2$ is CFL and not regular. What would be a good approach? | |
| Sep 5, 2022 at 8:24 | comment | added | tomato | That's where I struggle as I said in another answers comments. How do I proceed without using a specific example for a CFL language like $\{0^𝑛1^𝑛\}$? For a regular $L$ it would be easy because we could use Sigma*, but I have no clue what would be the way for a CFL language... | |
| Sep 4, 2022 at 21:22 | comment | added | Nathaniel | 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 20:23 | comment | added | tomato | 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 19:53 | comment | added | Nathaniel | $L\cup \{u\}$ is a superset of $L$ that is different of $L$. | |
| Sep 4, 2022 at 19:20 | comment | added | tomato | 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 17:52 | history | answered | Nathaniel | CC BY-SA 4.0 |