Does there exist an context free language L such that L∩L^R is not context free?

Question

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an example of $L$, but it seems the set of $L \cap L^R$ could only have palindromes (including languages like $aaa \ldots$) and the empty string. However, palindromes in $L \cap L^R$ are always context-free. May I ask if anyone could provide me an example of CFL $L$ such that $L\cap L^R$ is not context-free?

• Ben: The language that consists of any string that is a palindrome is context free. But that's not the same as saying the language of the specific strings you get from $L \cap L^R$ is context-free, merely because they are all palindromes.
• justhalf: Taken together, what Ben and the answer is saying is that $a^nb^na^n$ is a set of palindromic strings, but not context-free.
• Hendrik Jan: Perhaps I am mis-reading the question and a comment above, but strings in $L\cap L^R$ are not necessarily palindromic. Consider $L = \{ ab,ba\},ドル then $L\cap L^R = L$.

Answer 1

Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$.

In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera.

Note that we can get really fun things: For $ L = \{ a^n b^{2n} \mid n\ge 1 \}^* \;\cup\; b^+ {\cdot} \{ a^{2n} b^n \mid n\ge 1 \}^* {\cdot} a $ $L\cap L^R$ contains words of the form $ a^1 b^2 a^4 b^8 \dots b^{2^k} $ (and their mirror image).

Added. In fact, the trick above can be extended to "encode" all intersections of two arbitrary context-free languages. Let $K_1,K_2$ be context-free. Take a new special letter $\square$. Now take $L = \square K_1 \cup K_2^R\square$. Then

$L\cap L^R = \square (K_1\cap K_2) \; \cup\; (K_1^R\cap K_2^R)\square $

as words in $L$ are either marked at the start or at the end, depending whether they belong to $K_1$ or the reversal of $K_2$.

Answer 2

One of the conventional examples of languages that are not context-free is $X = \{ a^n b^n a^n | n \geq 0 \}$. You can use that to construct an example of what you are looking for by setting $L = \{ a^n b^n a^m | n,m \geq 0 \}$. $L$ is clearly context-free but $L \cap L^R = M$. You can use similar tricks to construct other conventional non-context-free languages, or at least variations of them.

• greybeard: Does this answer do more than spelling out part of Hendrink Jan's?