1
$\begingroup$

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")?

$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Jun 20 at 11:18
  • $\begingroup$ @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)? $\endgroup$ Jun 20 at 12:34
  • 2
    $\begingroup$ 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). $\endgroup$
    – Shaull
    Jun 20 at 13:15
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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