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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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. $\endgroup$– BenNov 20 at 0:05
-
$\begingroup$ 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. $\endgroup$– justhalfNov 20 at 2:55
-
1$\begingroup$ 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$. $\endgroup$– Hendrik JanNov 21 at 14:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ Does this answer do more than spelling out part of Hendrink Jan's? $\endgroup$ Nov 20 at 8:54