1
$\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$

1 Answer 1

1
$\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

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.