For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*,d(x,y) = k\}$ is context-free for some infinite regular language $A$ over the alphabet $\{0,1\}$.  

I think the statement is false. Intuitively, context-free grammars cannot keep track of the number of positions where strings differ, but I'm not sure how to use the pumping lemma for this case. If $k=1$, then I'd need show that the given language isn't context free for any infinite regular language $A$. If we consider the regular language generated by $0^*$ for instance, then the language would consist of all strings $0^n 2 y$ where $y$ has length $n$ and exactly one $1$. If $A$ were finite, obviously the given language would be context-free for all $k$ because it would be finite.  

This question was based off of this other post.

  • $\begingroup$ Was my answer helpful? Have you considered upvoting and accepting my answer? Please comment if my answer can be improved. (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    Jul 5, 2022 at 22:22

1 Answer 1


Let $F=\{x2y : |x| = |y|,\ x\in \{0\}^*,\ y\in\{0,1\}^*,\ d(x,y) = 1\}$, the language of all strings $0^n2y$ where $y$ consists of $n-1$ $0$s and one $1$.

Note that $F=\{0^p00^q20^q10^p: p\ge0, q\ge0\}$. Here is a context-free grammar for it.
    $S\to 0S0\mid 0T1$
    $T\to 0T0\mid 2$

Since $F$ is context-free, the proposition in the question is true.

On the other hand, the language $H_{A,k}=\{x2y^R : |x| = |y|,\ x\in A,\ y\in\{0,1\}^*,\ d(x,y) = k\}$ is always context-free when $A$ is regular. Note that $y^R$ instead of $y$ appears at the end of each word, so that we can construct a context-free grammar by synchronizing the generation of $x$ by a right linear grammar and the generation of $y^R$ by a corresponding left linear grammar, as pointed out by Hendrik Jan.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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