[Solved]: Show that $0^i$ where $i$ is a power of 2 is not context free

Problem Detail: I’m having difficulty trying to use the pumping lemma in order to show that $L= {0^i mid i text{ is a power of 2 }} $ is not context free. I”m starting by stating that $ s = 0^p$ and then $ s = uvxyz $ and that in order for a language to be context free it must follow the 3 conditions: $|vy| > 0$ , $|vxy|le p$ and for some $m ge 0, , uv^mxy^mz in L$. So I guess I”m struggling on how pumping something $uv^mxy^mz$ will not be in $L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in $L$. Any help greatly appreciated!

Asked By : MannfromReno

Answered By : Rick Decker

If you’re still confused, here’s the proof. Let $p$ be the integer of the Pumping Lemma and consider the string $0^{2^p}$. If $L$ was a CFL, then (since $2^pge p$) the PL would apply to $0^{2^p}$ we’d have $0^{2^p}=uvxyz$ with

$|vxy|le p$
$|vy| > 0$

So if we let $v=0^k, y = 0^j$, we have from (1), $k + j =|vy| le |vxy| le p$ and from (2), $k + j=|vy|>0$. In other words,

$0<k+jle p$

Now pump up: The PL assures us that $uv^2xy^2zin L$, and observe $$ |uv^2xy^2z| = 2^p+(k+j)le 2^p+p< 2^p+2^p=2^{p+1} $$ as long as $p>0$, so the pumped string $uv^2xy^2z$ has length strictly between $2^p$ and $2^{p+1}$. No such string can be in $L$, so we have a contradiction to the PL implication that $uv^2xy^2zin L$ and so our initial assumption, that $L$ was a CFL, must be false. You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language $L={0^{2^n}mid nge 0}$ is not regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32338 Ask a Question Download Related Notes/Documents