0
$\begingroup$

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

L = { 0n1k : 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.

$\endgroup$
2
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ That is the pumping lemma for regular languages, is it not? For CFL's, the pumping lemma breaks it down into 5 elements ($vwxyz$) as opposed to just 3 ($xyz$), with $|wxy| ≤ p$, $|wy| ≥ 1$, and $vw^ixy^iz ∈ L$ for all $i≥0$. $\endgroup$ – Tesla Nov 27 '13 at 23:16
  • 2
    $\begingroup$ As @Tesla says, this just shows that $L$ is not regular. $\endgroup$ – Brian M. Scott Nov 27 '13 at 23:55

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.