Is this language context-free?

Question

$L=\{ xcycz : x,y,z \in \{a,b\}^* \wedge xy, \ yz - \text{palindromes} \}$

Is $L$ context free language?

Answer 1

No, it is not. If you try to think about the limitations of context free grammars, you'll recall that doing one type of matching at a time is possible (e.g. $a^nb^n$) but when we need two or more at the same time, that's when things become impossible (e.g. $a^nb^nc^n$).

The language in question is similar in a way to $a^nb^nc^n$, in that when we ensure that $xy$ is a palindrome, at the same time as we're building the $y$ part we also need to use it for building up the $yz$ part, which isn't possible.

Here's a proof using the pumping lemma: let $n$ be the constant given by the pumping lemma and $z=a^nb^ncb^na^nca^nb^n \in L, |z| > n$. We can write $z=uvwxy$ such that $|vwx| \leq n, |vx| \geq 1$.

Thus there are 4 possibilities as to how $vwx$ looks like:

1. $vwx = a^tb^s$ where $t$ or $s$ are not both $0$.
2. $vwx = b^ta^s$ where $t$ or $s$ are not both $0$.
3. $vwx = b^tcb^s, t, s \geq 0$.
4. $vwx = a^tca^s, t, s \geq 0$.

It is left to show that every one of these can be pumped and lead to a contradiction that $z \in L$.