Are there context-free languages whose both intersection and complement of intersection are non-context-free?

Question

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 no 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).

Answer 1

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.

Answer 2

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.