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

Improve this question
$\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
    Commented Jun 20, 2021 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$
    – shantanu4raje
    Commented Jun 20, 2021 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
    Commented Jun 20, 2021 at 13:15

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – shantanu4raje
    Commented Jul 4, 2021 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$
    – Yuval Filmus
    Commented Jul 4, 2021 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$
    – shantanu4raje
    Commented Jul 4, 2021 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$
    – shantanu4raje
    Commented Jul 4, 2021 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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