After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one.
The language $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ \} $ is not Context-Free.
It is helpful to keep in mind the characterization $L= \{uv:|u|=|v|,d(u,v) \geq 2\}$ where d is the Hamming distance, proposed by @sdcvvc. What one needs to think about are 2 selected positions in each half string such that the corresponding symbols differ.
Then you consider a string $10^i10^j$ such that $i \lt j$ and $i+j$ is even. It is clearly in the language L, by cutting $u$ and $x$ anywhere between the two 1's. We want to pump that string on the first part between the 1's, so that it will become $10^j10^j$ which is not supposed to be in the language.
We first try to use Ogden's lemma, which is like the pumping lemma, but applies to $p$ or more distinguished symbols that are marked on the string, $p$ being the pumping length for marked symbols (but we can pump more if we pump unmarked symbols). The pumping marked-length $p$ depends only on the language. This attempt will fail, but the failure will be a hint.
We can then choose $i=p$ and we mark symbols on the first sequence of $i$ 0's. We know that none of the two 1's will be in the pump, because it can pump out once (exponent 0) instead of pumping in. And pumping out the 1's would get us out of the language.
However, we could be pumping on both sides of the second 1 as fast or even faster on the right side, so that the second 1 would never get across the middle of the string. Also Ogden's lemma does not fix an upper limit to the size of what is being pumped, so that it is not possible to organize the pumping so that we get the rightmost 1 exactly across the middle of the string.
We use a modified version of the lemma, here called Nash's Lemma, which can handle these difficulties.
We first need a definition (it probably has another name in the literature, but I do not know which - help is welcome). A string $u$ is said to be an erasure of a string $v$ iff it is obtained from $v$ by erasing symbols in $v$. We will note $\hat v$ the erasure of $v$.
Nash's Lemma : If $L$ is a context-free language, then there exists two numbers $p\gt0$ and $q\gt 0$ such that for any string $w$ of length at least $p$ in $L$, and every way of “marking” $p$ or more of the positions in $w$, $w$ can be written as $w=uxyzv$ with string $u$, $x$, $y$, $z$, $v$, such that
- $xz$ has at least one marked position,
- $xyz$ has at most $p$ marked positions, and
- there are 3 strings $\hat x$, $\hat y$, $\hat z$ such that
- $\hat x \prec x$, $\hat y \prec y$, $\hat z \prec z$,
- $1 \leq \mid \hat x \mid + \mid \hat z \mid \leq q$, $1 \leq \mid \hat y \mid \leq q$, and
- $u\hat x^i\hat y\hat z^iv$ is in $L$ for every $i \geq 0$.
Proof: Similar to the proof of Ogden's lemma, but the subtrees corresponding to the strings $y$ and $xz$ are pruned so that they do not contain any path with twice the same non-terminal. This necessarily limit the size of the generated strings by a constant $q$.
We modify the above proof attempt by marking the leftmost $p$ symbols 0, but they are followed by $2q$ symbols 0 to make sure that we pump in the left part between the two 1's. That make a total of $i = p + 2q$ 0's between the 1's.
What is left is to have chosen $j$ so that we can pump exactly the right number of 0's so that the two sequences are equal. But so far, the only constraint on $j$ is to be greater than $i$. And we also know that the number of 0's that are pumped at each pumping is between 1 and q. So let $h$ be product of the first $q$ integers (or just plainly their product). We choose $j=i+h$.
Hence, since the pumping increment $d$ - whatever it is - is in $[1,q]$, it divides $h$. Let $k$ be the quotient. If we pump exactly $k$ times, we get a string $10^j10^j$ which is not in the language. Hence L is not context-free.