0
$\begingroup$

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma.

So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can then pick a string of the form $w=0^{2^m}$

We know that $w=uvxyz$ where $|vxy| \leqslant m$ and $|vy| > 0$ and $uv^ixy^iz\in L$.

As the string is made of only zeros the only case we need to consider is : $vy = 0^j$, $j>0$.

If we take $i=2$ then we get $w'=uv^2xy^2z = 0^{2^m+j}$.

To show $w'\notin L$ we can show $2^{m}<2^m+j < 2^m$. I'm not sure how to show this part though. I thought that as $j$ is $|vy|$ and $|vxy| \leqslant m$ then $|vy| \leqslant m$ but im not sure where to go from here.

$\endgroup$
1