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

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?

• 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.
– Ben
Nov 20 at 0:05
• 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. Nov 20 at 2:55
• 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$. Nov 21 at 14:30

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$$.

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.

• Does this answer do more than spelling out part of Hendrink Jan's? Nov 20 at 8:54