Skip to main content
Post Closed as "Duplicate" by D.W.

Show that 0^i$0^i$ where i$i$ is a power of 2 is not context free

edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Tweeted twitter.com/#!/StackCompSci/status/526511008659931136
added 7 characters in body
Source Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

I'm having difficulty trying to use the pumping lemma in order to show that $ L= \{0^i|\,i\;is\,a\,power\,of\,2\,\} $$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$L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in L$L$. Any help greatly appreciated!

I'm having difficulty trying to use the pumping lemma in order to show that $ L= \{0^i|\,i\;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!

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!

added 1 character in body
Source Link
Loading
Source Link
Loading