Context free grammar and pumping lemma

Question

I have a language $ L = { (b_i \# b_{i+1} ) } $ where $ b_i \ge 1 $ and $ b_i $ is binary representation of number $ i \ge 1 $

I have a word $ w = 10^N1^N1 \# 10^{N-1}10^N0$ and $ w = uvxyz $

Could someone give me a hint how to use pumping lemma ?

Answer 1

The pumping lemma for CFLs states that for a CFL $L$ there is a constant $N$ such that all $\sigma \in L$ which are longer than $N$ can be written $\sigma = u v x y z$ such that $\lvert v x y \rvert \le N$ where $v y$ isn't empty and for all $k \in \mathbb{N}_0$ we have $u v^k x y^k z \in L$. You want to prove $L = \{ b_i \# b_{i + i} \colon i \ge 0 \}$ where $b_i$ is $i$ written in binary isn't context free.

The proof is by contradiction. Suppose $L$ is context free, and call the constant of the lemma $N$.

You select $\sigma = 1 0^N 1^{N + 1} \# 1 0^{N - 1} 1 0^{N + 1}$. Any viable split will have the $\#$ in $x$ (if it is in $v$ or $y$ by pumping you get more than one $\#$, and if it is in the head $u$ or the tail $z$, you are changing only one of the two numbers by pumping). Now $v$ and $y$ have lengths less than $N$, so $v$ is only ones, and if $u v^k x y^k z$ is to keep the general form of $1 0^* 1^* \# 1 0^* 1 0^*$, $y$ is made of zeroes. But then leaving out $v$ and $y$ (select $k = 0$) gives two numbers written in binary that don't match your condition (too few zeroes at the right or too few ones at the left). Contradiction.