Intersection of context-free language and its reversal

354 Views Asked by At

I know that intersection of two context-free languages is not always context-free and the following problem:

Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ?

is undecidable. But is that true in particular case when we know that $B = \{ w^{R} | w \in A \}$?

1

There are 1 best solutions below

1
On

If $A$ contains a palindromic string $w$ then $w^R=w$. So in this case, $A \cap B \neq \varnothing$. But if $A$ doesn't contain any palindromic string, we cannot find a common element of $A$ and $B$.