Is a divisibility language context free?

Question

I am working to see if this language would be context free:

L = { 0ⁿ1^k : n/k is an integer }

After playing with it for a little while, I believe that the language is not context free. Now I am looking to use the pumping lemma to prove that it is not, but am struggling a bit to apply it to this language, which is making me question whether it might be a CFL.

Is this language context free? If not, how should I approach using the pumping lemma to prove that it is not.

Answer 1

Let $p$ be the pumping length and pick $k>p$. As $0^k1^k\in L$, we can write $0^k1^k=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $xy^iz\in L$ for all $i\ge 0$. We conclude that $x=0^r, y=0^s$ wirh $r\ge0$, $s\ge 1$. Then $xy^0z=0^{k-s}1^k\notin L$.

Answer 2

Suppose that $L$ is context-free, let $p$ be the pumping length, and let $w=0^{3(p+1)}1^{p+1}$. By the pumping lemma we can write $w=uvxyz$, where $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for each $k\ge 0$.

Let $r$ be the number of $0$’s in $vy$, and $s$ the number of $1$’s. Note that if either $v$ or $y$ contains both $0$’s and $1$’s, then $uv^2xy^2z$ has at least one $1$ preceding a $0$ and cannot be in $L$, so we may assume that $v=0^r$ and $y=1^s$. Thus, $$uv^kxy^kz=0^{3(p+1)+(k-1)r}1^{p+1+(k-1)s}$$ for each $k\ge 0$.

If $r<s$, then for sufficiently large $k$ the word $uv^kxy^kz$ has more $1$’s than $0$’s and cannot be in $L$, so we must have $r\ge s$. The excess of $0$’s over $1$’s in $uv^kxy^kz$ is

$$\big(3(p+1)+(k-1)r\big)-\big(p+1+(k-1)s\big)=2(p+1)+(k-1)(r-s)\;,$$

and in order for $uv^kxy^kz$ to be in $L$, this must be a multiple of $p+1+(k-1)s$, the number of $1$’s. That is, for each $k\ge 0$ we must have

$$\frac{2(p+1)+(k-1)(r-s)}{p+1+(k-1)s}\in\Bbb Z\;.\tag{1}$$

If $r-s<s$ this is impossible: for sufficiently large $k$ the denominator of $(1)$ will exceed the numerator. Thus, we must have $r=2s$, so that the excess of $0$’s over $1$’s in $uv^kxy^kz$ is $$2(p+1)+(k-1)s\;,$$ and

$$\frac{2(p+1)+(k-1)s}{p+1+(k-1)s}\in\Bbb Z$$

for each $k\ge 0$, where $0<s<p$. Can you see why this is impossible? There’s a hint in the spoiler-protected block below, if you need one.

What happens in the limit as $k\to\infty$?