Skip to main content
20 of 40
deleted 272 characters in body
babou
  • 19.6k
  • 41
  • 76

After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one.

There may be some further aspects to work out as I am not completely sure I am mastering all the subtleties of Ogden's lemma (I am still checking a proof for another language that seems too complicated compared to the proof I am giving here), but I think that this is at least the direction for a proof

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.

This can be done using Ogden 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.

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 , so that the second 1 would never get across the middle so that we pump only in that sequence to grow it.

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 p. So let $h$ be le least common multiple of the first $p$ integers (or just plainly their product). We choose $j=i+h$.

Hence, since the pumping increment $d$ - whatever it is - is in $[1,p]$, 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.

babou
  • 19.6k
  • 41
  • 76