If the language is context free?

Question

i believe intuitively the following language is CF. But there is a book (without more description) that states the language is not CF. If I'm in a wrong way?

$L=\{W_1cW_2 | W_1,W_2 \in (a+b)^* W_1 \neq W_2^R\}$

Regards.

Answer 1

The language is in fact context-free. The idea is if the words are not the reverse of each other, there is at least one position which is not mirrored. A PDA or a CFG would break the word as follows: $W_1cW_2 = Ud_1Vd_2U^R$ where $U\in \{a,b\}^*$ and $d_1$ and $d_2$ are non-matching symbols. The PDA pushes $Ud_1$ (guessing non-deterministically where to stop) and then ignores $V$, and again non-deterministically guesses where to read $d_2$ and checks if $d_2 \neq d_1$. Then it continues with reading $U^R$ while popping and checking for equal symbols.