2
$\begingroup$

It is well known that context-free languages are not closed under intersection or complement. But what about context-free languages $L_1$ and $L_2$, such that $L_1 \cap L_2$ as well as $\left( L_1 \cap L_2 \right)^C$ are not context-free languages.

I can think of many examples of two context-free languages whose intersection is non-context-free, but I can't come up with an example with complement of intersection being also non-context-free (e.g. popular counterexample for closure under intersection, where $L_1 = \{ a^n b^n c^m \mid n, m \geq 0 \}$ and $L_2 = \{ a^m b^n c^n \mid n, m \geq 0 \}$ with $L_1 \cap L_2 = \{ a^n b^n c^n \mid n \geq 0 \}$ discussed here: Why are CFLs not closed under intersection? and here: Prove complement a^nb^nc^n is contextfree).

I suspect there are not such languages $L_1$ and $L_2$, but I'm far from being sure. The only thing I'm certain of is that at least one of languages $L_1^C$ and $L_2^C$ would have to be non-context-free (otherwise, as a result of closure under union, language $L_1^C \cup L_2^C = \left( L_1 \cap L_2 \right)^C$ would be context-free).

$\endgroup$

2 Answers 2

2
$\begingroup$

Here is a recipe to construct such a language, using examples we know. Start with a context-free language $K_0$ such that its complement $K_0^C$ is not context free. Also consider two context-free languages $K_1$ and $K_2$ such that their intersection $K_1\cap K_2$ is not context-free.

Note that for any language $K = a{\cdot} K_a \cup b{\cdot}K_b$, we have $K^C = a{\cdot} K^C_a \cup b{\cdot}K^C_b \cup \{\varepsilon \}$, which intuitively means that we can separate complements using the first symbol of the strings.

Using this observation, consider $L_1 = a{\cdot}K_0 \cup b{\cdot}K_1$, and likewise $L_2 = a{\cdot}K_0 \cup b{\cdot}K_2$.

First, $L_1\cap L_2$ is not context-free, because $(L_1\cap L_2) \cap b{\cdot}\Sigma^* =b\cdot(K_1\cap K_2)$ is not context-free.

Similarly $(L_1\cap L_2)^C$ is not context-free because $(L_1\cap L_2)^C\cap a{\cdot}\Sigma^* = a{\cdot}K^C_0$.

Perhaps someone else will find an elegant direct example.

$\endgroup$
1
  • $\begingroup$ Thanks a lot, this construction is good enough for me. I was just curious whether there do or don't exist such languages. $\endgroup$
    – Buco
    Dec 5, 2023 at 8:04
2
$\begingroup$

We can build a specific example over the alphabet $\{a,b,c\}$ as follows. Let $L_1 = \{ a^k b^m c^j \mid j < m \lor k < m \}$ and $L_2 = \{ a^k b^m c^j \mid k < 2m \}$. Obviously, $L_1 \cap L_2 = \{ a^k b^m c^j \mid ( j < m \land k < 2m ) \lor k < m \}$. We are going to prove that both $L_1 \cap L_2$ and $(L_1 \cap L_2)^C$ are non-context-free. The following proof consists in two straightforward applications of the pumping lemma (using intersection with a simple regular language where necessary).

Suppose to the contrary that $L_1 \cap L_2$ is context-free. The pumping lemma yields a number $p$. We consider the word $a^{2p+1} b^{p+1} c^p$, which is in $L_1 \cap L_2$. The pumping lemma gives a partition $uvwxy = a^{2p+1} b^{p+1} c^p$. If neither $v$ nor $x$ contains $b$, then we put $n=2$ and note that $uvvwxxy \notin L_1 \cap L_2$. Otherwise we put $n=0$ and consider the word $uwy$. If neither $v$ nor $x$ contains $a$, then $uwy$ contains $2p+1$ letters $a$, which is too many compared to the reduced number of letters $b$. Suppose that $v$ or $x$ contains $a$. Then neither of them contains $c$, because the letters $c$ are too far from the letters $a$. Let $uwy = a^k b^m c^j$. We see that $k = 2p + 1 - |vx|_a$, $m = p + 1 - |vx|_b$, $j = p$. Thus, $j = p \geq m$. On the other hand, $k \geq p + 1 \geq m$. Thus, $uwy \notin L_1 \cap L_2$. In all cases we have obtained a contradiction, and so $L_1 \cap L_2$ is not context-free.

Now suppose to the contrary that $(L_1 \cap L_2)^C$ is context-free. Consider the language $L = (L_1 \cap L_2)^C \cap \{ a^k b^m c^j \mid k \geq 0,\ m \geq 0,\ j \geq 0 \}$. The intersection of a context-free language with a regular language is always context-free. Applying the pumping lemma for context-free languages to $L$, we obtain a number $p$. We consider the word $a^p b^p c^p$, which is in $L$. The pumping lemma gives a partition $uvwxy = a^p b^p c^p$. If neither $v$ nor $x$ contains $b$, then we put $n=0$ and see that $uwy \in L_1 \cap L_2$, whence $uwy \notin L$. Otherwise we put $n=2$ and consider the word $uvvwxxy$. If neither $v$ nor $x$ contains $a$, then $uvvwxxy$ contains $p$ letters $a$ and more that $p$ letters $b$, which yields $uvvwxxy \in L_1 \cap L_2$, whence $uvvwxxy \notin L$. Suppose that $v$ or $x$ contains $a$. Then neither of them contains $c$, because the letters $c$ are too far from the letters $a$. Let $uvvwxxy = a^k b^m c^j$. We see that $k = p + |vx|_a$, $m = p + |vx|_b$, $j = p$. Thus, $j = p < m$. On the other hand, $k \leq 2p < 2m$. Thus, $uvvwxxy \in L_1 \cap L_2$, whence $uvvwxxy \notin L$. In all cases we have obtained a contradiction, and so $(L_1 \cap L_2)^C$ is not context-free.

$\endgroup$
1
  • $\begingroup$ I upvoted both answers but would like to see this answer accepted. $\endgroup$ Mar 2 at 19:57

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.