Timeline for Show that $0^i$ where $i$ is a power of 2 is not context free [duplicate]
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2021 at 1:32 | history | closed | D.W.♦ | Duplicate of Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$ | |
| S Apr 22, 2015 at 6:34 | history | suggested | Alejandro Sazo | CC BY-SA 3.0 |
edited title with latex syntax
|
| Apr 22, 2015 at 1:03 | review | Suggested edits | |||
| S Apr 22, 2015 at 6:34 | |||||
| Oct 27, 2014 at 13:45 | comment | added | Raphael | Our reference question may provide some clues. | |
| Oct 27, 2014 at 13:44 | history | edited | Raphael |
edited tags
|
|
| Oct 26, 2014 at 23:09 | history | tweeted | twitter.com/#!/StackCompSci/status/526511008659931136 | ||
| Oct 26, 2014 at 22:49 | vote | accept | MannfromReno | ||
| Oct 26, 2014 at 21:18 | answer | added | Rick Decker | timeline score: 3 | |
| Oct 26, 2014 at 18:12 | comment | added | MannfromReno | Hmm, you're right, we wouldn't know what u,v,w,x and y are. Now I might be more lost, I'll keep reviewing. Thank you. | |
| Oct 26, 2014 at 17:26 | answer | added | Yuval Filmus | timeline score: 2 | |
| Oct 26, 2014 at 17:22 | history | edited | Juho | CC BY-SA 3.0 |
added 7 characters in body
|
| Oct 26, 2014 at 17:18 | comment | added | Roi Divon | It's not true. you don't know what $u,v,w,x$ and $y$ are. Try showing that $2^k < |uv^2wx^2y| < 2^{k+1}$ | |
| Oct 26, 2014 at 17:13 | comment | added | MannfromReno | Okay that makes sense, so with $uv^2wx^2y$ the length of this would be an odd length if u, v, and y are all raised to 1, so $u^1v^2x^1y^2z^1$ is an odd length. | |
| Oct 26, 2014 at 17:10 | history | edited | MannfromReno | CC BY-SA 3.0 |
added 1 character in body
|
| Oct 26, 2014 at 17:03 | comment | added | Roi Divon | Asumme $L$ is CFL. Let $k$ be the constant of the pumping lemma. let $z=0^{2^k} \in L$.. from the lemma we get that $z=uvwxy$. Consider $uv^2wx^2$. by the lemma, it's in $L$. What can you say about the length of this word? Try prooving that the length isn't a power or 2 | |
| Oct 26, 2014 at 16:35 | review | First posts | |||
| Oct 26, 2014 at 16:41 | |||||
| Oct 26, 2014 at 16:32 | history | asked | MannfromReno | CC BY-SA 3.0 |