Timeline for Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2021 at 6:14 | comment | added | shantanu4raje | The idea of using "co-context-free" instead of generalising into context-sensitive finally made me understand. This is exactly what I was looking for. | |
| Jul 4, 2021 at 6:11 | vote | accept | shantanu4raje | ||
| Jul 4, 2021 at 5:29 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 649 characters in body
|
| Jul 4, 2021 at 5:24 | comment | added | shantanu4raje | The 1st approach doesn't actually claim that $L_2^c$ is not context-free. It claims that it is not "definitely" context-free. It could be but not always. It is already mentioned in my question after that line. | |
| Jul 4, 2021 at 5:05 | comment | added | Yuval Filmus | The first approach is actually wrong, since it claims that $L_2^c$ is not context-free. It could be. | |
| Jul 4, 2021 at 5:03 | comment | added | shantanu4raje | I understand that "being context-sensitive doesn't preclude being context-free" because context-free languages are a subset of context-sensitive languages. But I am not sure of the reason of the 1st approach being weaker than the 2nd one. My guess is - the generalization of CFL into CSL (to avoid the non-closure of CFL under complementation) makes it weak. Is it correct? | |
| S Jul 2, 2021 at 11:41 | history | answered | Yuval Filmus | CC BY-SA 4.0 | |
| S Jul 2, 2021 at 11:41 | history | made wiki | Post Made Community Wiki by Yuval Filmus |