Is this language context-free? $L=\{ xcycz : x,y,z \in \{a,b\}^* \wedge xy, \ yz  - \text{palindromes} \}$
Is $L$ context free language?
 A: 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:


*

*$vwx = a^tb^s$ where $t$ or $s$ are not both $0$.

*$vwx = b^ta^s$ where $t$ or $s$ are not both $0$.

*$vwx = b^tcb^s, t, s \geq 0$.

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