13
$\begingroup$

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')>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.

Improve this question
$\endgroup$
4
  • $\begingroup$ $L\cap R'$ is actually easier, as it is exactly the words that are not of the form $ww$ (intersected by $R'$). $\endgroup$
    – domotorp
    Jan 17, 2019 at 22:39
  • $\begingroup$ @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$) $\endgroup$
    – Marzio De Biasi
    Jan 17, 2019 at 23:29
  • $\begingroup$ 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.) $\endgroup$
    – domotorp
    Jan 18, 2019 at 6:10
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 8, 2019 at 18:31

1 Answer 1

Reset to default
4
$\begingroup$

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<n/2\}$.

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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$? $\endgroup$
    – Marzio De Biasi
    Jan 17, 2019 at 0:58
  • $\begingroup$ $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). $\endgroup$
    – domotorp
    Jan 17, 2019 at 9:28
  • $\begingroup$ Does this answer the full question? $\endgroup$
    – Michaël Cadilhac
    Jan 17, 2019 at 15:48
  • $\begingroup$ @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) $\endgroup$
    – Marzio De Biasi
    Jan 17, 2019 at 19:00
  • $\begingroup$ @Michael: No. $~$ $\endgroup$
    – domotorp
    Jan 17, 2019 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.