<p>The intersection with <span class="math-container">$R=\{0^*10^*10^*10^*\mid$</span> even length words<span class="math-container">$\}$</span> is context-free, because a PDA <em>can</em> remember two positions, in a way. Anyhow, let's first see what this language <span class="math-container">$L$</span> is. Its complement is
<span class="math-container">$R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$</span>. Therefore,
<span class="math-container">$L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge  c\ne n/2 \wedge a+d\ne n/2\}$</span>. We can rewrite this as
<span class="math-container">$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\}$</span>.</p>

<p>The first <span class="math-container">$3$</span> cases can be easily verified, and so can the fourth one.</p>

<p><span class="math-container">$b&gt;n/2$</span>: 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.</p>

<p><span class="math-container">$c&gt;n/2$</span>: Same.</p>

<p><span class="math-container">$a+d&gt;n/2$</span>: 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.</p>

<p><span class="math-container">$b,c,a+d&lt;n/2$</span>: 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 <span class="math-container">$a+n/2$</span> (guessed non-deterministically, somewhere between second and third 1). From then on pop the stack.</p>

CC BY-SA 4.0
2019-01-17T00:58:06.620Z
Thanks domotorp, I'm reading your idea; I think $R \setminus L$ is $\{ 0^a 1 0^b 1 0^{c'} 0^{c''} 1 0^d \mid \ (n/2=a+b+c'=c''+d+1) \land [(a= c'')\lor (c' = d) \}$ (two 1s on the left half) union its reverse (two 1s on the right half). So how do you get $b=n/2 \vee c=n/2 \vee a+d=n/2$?
Marzio De Biasi
CC BY-SA 4.0
2019-01-17T09:28:13.883Z
$R\subset L$ is that the HamDist is at most $1$. This happens exactly if two of the three 1's match, i.e., one is in the same position in the first half, as the other is in the second half. If these two 1's are the first and second 1's, then we get $b=n/2$, if they are the second and third 1's, we get $c=n/2$, and if they are the first and third 1's, we get $b+c=n/2$, or equivalently, $a+d=n/2$ (where I'm cheating a bit with some constant $\pm 1$'s).
domotorp
CC BY-SA 4.0
2019-01-17T15:48:43.940Z
Does this answer the full question?
Michaël Cadilhac
CC BY-SA 4.0
2019-01-17T19:00:53.657Z
@domotorp: ok I got it, thanks! Another doubt: from $L \cap R  = \{...b \neq n/2 \land c \neq n/2...\}$ (which is ok) you write $L \cap R = \{ ...b > n/2 \lor c > n/2 \lor b,c < n/2 \}$ but, is it equivalent to: $L \cap R = \{... (b < n/2 \lor b >n/2) \land (c < n/2 \lor c >n/2)\}$? ($a+d$ condition omitted)
Marzio De Biasi
CC BY-SA 4.0
2019-01-17T19:51:39.860Z
@Michael: No. $~$
domotorp
CC BY-SA 4.0
2019-01-17T19:55:42.613Z
@Marzio: Yes. Maybe I should have mentioned, but $n$ is the length of the word, so it's not possible for two of the variables to be $>n/2$.
domotorp
CC BY-SA 4.0
2019-01-17T20:57:52.780Z
N.i.c.e.! I updated the question .
Marzio De Biasi
CC BY-SA 4.0
2019-01-16T21:26:26.083Z
2019-01-16T21:26:26.083Z
domotorp
<p>After reading the recent question <a href="https://cstheory.stackexchange.com/q/42194/3247">"Is the complement of <span class="math-container">$\{ www \mid ...\}$</span> context-free?"</a>; I remembered a similar problem I wasn't able to disprove:</p>

<blockquote>
  <p>Is <span class="math-container">$L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')&gt;1 \}$</span> context free?</p>
</blockquote>

<p>Here we require that the two strings differ in at least two positions (the Hamming distance must be greater than <span class="math-container">$1$</span>).</p>

<p>It is context-free if we require that <span class="math-container">$HamDist(w,w')\geq 1$</span> (i.e. the two strings must simply be different).</p>

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

<p><strong>Update:</strong> if we intersect <span class="math-container">$L$</span> with the regular <span class="math-container">$R = \{  0^*10^*10^*10^* \}$</span> we get a context-free language as showed by domotorp in his answer; a slightly more complex <span class="math-container">$L \cap R' $</span> with  <span class="math-container">$R' = \{  0^*10^*10^*10^*10^*10^* \}$</span> (one more <span class="math-container">$1$</span> to "keep track" of) still suggest that <span class="math-container">$L$</span> should not be context-free. </p>

CC BY-SA 4.0
2019-01-17T22:39:46.827Z
$L\cap R'$ is actually easier, as it is exactly the words that are not of the form $ww$ (intersected by $R'$).
domotorp
CC BY-SA 4.0
2019-01-17T23:29:54.823Z
@domotorp: right! changed to odd fixed $1$s (unless your answer could be adapted also to  $\{ (0^* 1 0^*)^k \}$, for any fixed odd $k$)
Marzio De Biasi
CC BY-SA 4.0
2019-01-18T06:10:05.770Z
One final comment: It doesn't help to start with leading zero's, as context-free languages are closed for all sorts of cyclic shifts. You could just push them to the stack, mark the last one with a special symbol, do the rest of the algorithm pretending that the stack starts there, and at the end empty it. (This uses $\epsilon$-transitions, but that's also easy that such PDA are equivalent to the ones without.)
domotorp
CC BY-SA 4.0
2019-02-08T18:31:02.517Z
it might be simpler to think about {0,1,2} alphabet and consider strings with exactly two 1s and two 2s. It is in not in your language if the distance between 1s and the distance between 2s are both n.
Kaveh
<fl.formal-languages><context-free>
Is { ww' | HamDist(w,w')>1 } context-free?
Marzio De Biasi
# Is { ww' | HamDist(w,w')>1 } context-free?

(Asked by: username_0 on 2019-01-14)

After reading the recent question ["Is the complement of $\{ www \mid ...\}$ context-free?"](https://cstheory.stackexchange.com/q/42194/3247); 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')>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 username_1 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.

**Tags:** fl.formal-languages, context-free

> **Comments:**
> **username_1**: $L\cap R'$ is actually easier, as it is exactly the words that are not of the form $ww$ (intersected by $R'$).  
> **username_0**: @username_1: right! changed to odd fixed $1$s (unless your answer could be adapted also to  $\{ (0^* 1 0^*)^k \}$, for any fixed odd $k$)  
> **username_1**: One final comment: It doesn't help to start with leading zero's, as context-free languages are closed for all sorts of cyclic shifts. You could just push them to the stack, mark the last one with a special symbol, do the rest of the algorithm pretending that the stack starts there, and at the end empty it. (This uses $\epsilon$-transitions, but that's also easy that such PDA are equivalent to the ones without.)  
> **username_2**: it might be simpler to think about {0,1,2} alphabet and consider strings with exactly two 1s and two 2s. It is in not in your language if the distance between 1s and the distance between 2s are both n.  

---

## 1 answers

### Answer by username_1 on 2019-01-16. Score: 4

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> n/2 \vee c> n/2 \vee a+d> n/2 \vee b,c,a+d.

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

$b>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>n/2$: Same.

$a+d>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: 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.

> **Comments:**
> **username_0**: Thanks username_1, I'm reading your idea; I think $R \setminus L$ is $\{ 0^a 1 0^b 1 0^{c'} 0^{c''} 1 0^d \mid \ (n/2=a+b+c'=c''+d+1) \land [(a= c'')\lor (c' = d) \}$ (two 1s on the left half) union its reverse (two 1s on the right half). So how do you get $b=n/2 \vee c=n/2 \vee a+d=n/2$?  
> **username_1**: $R\subset L$ is that the HamDist is at most $1$. This happens exactly if two of the three 1's match, i.e., one is in the same position in the first half, as the other is in the second half. If these two 1's are the first and second 1's, then we get $b=n/2$, if they are the second and third 1's, we get $c=n/2$, and if they are the first and third 1's, we get $b+c=n/2$, or equivalently, $a+d=n/2$ (where I'm cheating a bit with some constant $\pm 1$'s).  
> **username_3**: Does this answer the full question?  
> **username_0**: @username_1: ok I got it, thanks! Another doubt: from $L \cap R  = \{...b \neq n/2 \land c \neq n/2...\}$ (which is ok) you write $L \cap R = \{ ...b > n/2 \lor c > n/2 \lor b,c < n/2 \}$ but, is it equivalent to: $L \cap R = \{... (b < n/2 \lor b >n/2) \land (c < n/2 \lor c >n/2)\}$? ($a+d$ condition omitted)  
> **username_1**: @Michael: No. $~$  
> **username_1**: @Marzio: Yes. Maybe I should have mentioned, but $n$ is the length of the word, so it's not possible for two of the variables to be $>n/2$.  
> **username_0**: N.i.c.e.! I updated the question .  

---

