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

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

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.

• I upvoted both answers but would like to see this answer accepted. Commented Mar 2 at 19:57

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.

• Thanks a lot, this construction is good enough for me. I was just curious whether there do or don't exist such languages. Commented Dec 5, 2023 at 8:04