# Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive

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:

1. $$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.
2. 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")?

• Why do you see a discrepancy? The first approach is a weaker attempt, so you don't get much from it, but in the second approach you simply get a stronger result (remember that context-free languages are in particular, context-sensitive). Also, be careful with the term "context-sensitive", because it doesn't mean "not context-free", it's just a different computational model. Jun 20 at 11:18
• @Shaull, I understand that context-free languages are basically a subset of context-sensitive languages. I have also written it in first approach "it may also be context-free, but not definitely". What I don't understand is what makes the first approach weaker than the second one. Is it the generalization of CFL into CSL (to avoid the non-closure of CFL in complementation)? Jun 20 at 12:34
• The first approach is weaker simply because you're using weaker results: you're not using de-Morgan, and you're only using the fact that CSL are closed under union (instead of the stronger argument that the intersection of a regular language and a CFL is a CFL). Jun 20 at 13:15

There is no discrepancy in the two methods. The first method shows that $$L := \overline{\overline{L_1} \cup \overline{L_2}}$$ is context-sensitive. The second method shows the stronger result that $$L$$ is context-free. Both of these are consistent. Compare the following: $$1 + 1 \leq 1 + 2 = 3 \Longrightarrow 1 \leq 3 \\ 1 + 1 \leq 2$$ The first inequality shows that $$x := 1 + 1$$ satisfies $$x \leq 3$$. The second inequality is stronger, showing that $$x \leq 2$$. There is no discrepancy here. The second inequality is simply better.

The term context-sensitive is somewhat of a misnomer. Being context-sensitive doesn't preclude being context-free. In particular, every context-free language is also context-sensitive.

Here is how to cut the slack in your first argument:

1. Since $$L_1$$ is regular, $$L_1^c$$ is regular.
2. Since $$L_2$$ is context-free, $$L_2^c$$ is co-context-free (a language is co-context-free if its complement is context-free).
3. Since $$L_1^c$$ is regular and $$L_2^c$$ is co-context-free, so is $$L_1^c \cup L_2^c$$.
4. Hence $$(L_1^c \cup L_2^c)^c$$ is context-free.

In this case we were lucky to find classes of languages which tightly describe all intermediate steps. Sometimes we are not as lucky, and we need to find a different of proving that a certain language, constructed in a certain way, belongs to a certain language class.

• 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? Jul 4 at 5:03
• The first approach is actually wrong, since it claims that $L_2^c$ is not context-free. It could be. Jul 4 at 5:05
• 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 at 5:24
• 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 at 6:14