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

## 1 Answer

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.
– Buco
Dec 5, 2023 at 8:04