[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^p\ge p$) the PL would apply to $0^{2^p}$ we'd have $0^{2^p}=uvxyz$ with

1. $|vxy|\le p$
2. $|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+j\le p$

Now pump up: The PL assures us that $uv^2xy^2z\in 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^2z\in 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 n\ge 0\}$ is not regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32338

 Ask a Question

 Download Related Notes/Documents