1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Matan Halfon Apr 8 at 17:26
  • $\begingroup$ Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know. $\endgroup$ – Yuval Filmus Apr 8 at 17:27
  • $\begingroup$ If you don't know something, why not look it up? Be curious. $\endgroup$ – Yuval Filmus Apr 8 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 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 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.