Is { ww' | HamDist(w,w')>1 } context-free? After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove:


  Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')&gt;1 \}$ context free?


Here we require that the two strings differ in at least two positions (the Hamming distance must be greater than $1$).

It is context-free if we require that $HamDist(w,w')\geq 1$ (i.e. the two strings must simply be different).

I suspect that the language is not context-free: if we intersect it with the regular  $0^*10^*10^*10^*$ we get cases in which a PDA should "remember" two positions in reverse order after reaching the half of the string.

Update: if we intersect $L$ with the regular $R = \{  0^*10^*10^*10^* \}$ we get a context-free language as showed by domotorp in his answer; a slightly more complex $L \cap R' $ with  $R' = \{  0^*10^*10^*10^*10^*10^* \}$ (one more $1$ to "keep track" of) still suggest that $L$ should not be context-free.
The intersection with $R=\{0^*10^*10^*10^*\mid$ even length words$\}$ is context-free, because a PDA can remember two positions, in a way. Anyhow, let's first see what this language $L$ is. Its complement is
$R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$. Therefore,
$L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge  c\ne n/2 \wedge a+d\ne n/2\}$. We can rewrite this as
$L=\{0^a10^b10^c10^d\mid b&gt; n/2 \vee  c&gt; n/2 \vee a+d&gt; n/2 \vee b,c,a+d&lt;n/2\}$.

The first $3$ cases can be easily verified, and so can the fourth one.

$b&gt;n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the second 1. From then on pop the stack.

$c&gt;n/2$: Same.

$a+d&gt;n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the third 1. From then on pop the stack.

$b,c,a+d&lt;n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach $a+n/2$ (guessed non-deterministically, somewhere between second and third 1). From then on pop the stack.