# Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $$L$$ is such that for every context-free language $$L_0$$, the language $$L \cap L_0$$ is context-free, then $$L$$ is regular.

I haven't managed to prove this, but I'm pretty sure there is no counterexample.

Let $$L = \{a^n b^n : n \geq 0\}$$, and let $$L_0$$ be an arbitrary context-free language. Define $$L_1 = L_0 \cap a^* b^*$$, and note that $$L_1$$ is context-free and $$L \cap L_0 = L \cap L_1$$. Let $$S = \{(i,j) : a^i b^j \in L_1\}$$.
According to Parikh's theorem, the set $$S$$ is semilinear. The set $$D = \{(n,n) \geq 0\}$$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $$S \cap D$$ is also semilinear. Since $$S \cap D$$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $$F$$, a modulus $$m \geq 1$$ and a subset $$A \subseteq \{0,\ldots,m-1\}$$ such that $$L \cap L_1 = F \Delta \{ a^n b^n : n \bmod m \in A \},$$ where $$\Delta$$ is symmetric difference. It is easy to check that $$\{a^nb^n : n \bmod m \in A\}$$ is context-free, and so $$L \cap L_1$$ is context-free.
Summarizing, we have shown that $$L$$ is a non-regular language which satisfies your condition.
• I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here? – Kai Apr 9 at 12:13
• To simplify the end of the proof, for any semilinear set $T\subseteq\mathbb{N}^2$ it is easy to show that $L=\{a^i b^j : (i,j)\in T\}$ is a context-free language by explicitly constructing a grammar. This shows that any non-regular context-free language that is contained in $a^* b^*$ can be used as a counter example. – Ido Apr 16 at 13:54