I came across the following question:
Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \cup L_2^c)^c$? Is it context-free?
I tried to solve it in two different ways:
- $L_1^c$ is also regular because regular languages are closed under complementation, but $L_2^c$ is not context-free because context-free languages are not closed under complementation, so, it is context-sensitive (it may also be context-free, but not definitely). Also the union of a regular language and a context-sensitive language is context-sensitive. So, $(L_1^c \cup L_2^c)^c$ is context-sensitive.
- Applying DeMorgan's Law, $(L_1^c \cup L_2^c)^c$ becomes $L_1 \cap L_2$, which is clearly context-free.
Why is the discrepancy there between the two methods? What mistake am I making in the first approach (because the answer is "context-free")?