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.


1 Answer 1


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.

  • $\begingroup$ i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot $\endgroup$ Apr 8, 2019 at 17:26
  • $\begingroup$ Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know. $\endgroup$ Apr 8, 2019 at 17:27
  • $\begingroup$ If you don't know something, why not look it up? Be curious. $\endgroup$ Apr 8, 2019 at 21:42
  • $\begingroup$ I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here? $\endgroup$
    – Kai
    Apr 9, 2019 at 12:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ido
    Apr 16, 2019 at 13:54

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.