Timeline for How to find the pumping length of a context-free language?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 15, 2013 at 3:00 | review | Community Evaluations | |||
| May 22, 2013 at 3:00 | |||||
| Apr 12, 2013 at 13:13 | answer | added | Luke Mathieson | timeline score: 3 | |
| Apr 10, 2013 at 9:01 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags; edited title
|
| Apr 10, 2013 at 9:00 | comment | added | Raphael | Look at the proof of the Pumping Lemma, the answer is there. Note that "the" Pumping length is not unique; clearly, for any Pumping lengths $p$ all $n \geq p$ are also Pumping lengths. Therefore, $2^{100} $ is probably a correct answer, if uninstructive. | |
| Apr 10, 2013 at 7:55 | history | tweeted | twitter.com/#!/StackCompSci/status/321894278651604992 | ||
| Apr 10, 2013 at 6:36 | comment | added | Luke Mathieson | @YuvalFilmus, that would be the most sensible question I guess. It would've been interesting trying to show a CFG gives a non-context free language ;). | |
| Apr 10, 2013 at 6:25 | comment | added | Yuval Filmus | @Luke I think he's trying to answer an assignment question which is precisely this - what is the pumping length $p$ corresponding to the grammar. That's how I interpret the sentence "please explain how you actually got it from the grammar". | |
| Apr 10, 2013 at 6:23 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
edited title
|
| Apr 10, 2013 at 6:06 | history | edited | Luke Mathieson | CC BY-SA 3.0 |
Variable T renamed to C
|
| Apr 10, 2013 at 5:44 | comment | added | Ran G. | if you just need to prove $L$ is not CFL, you usually don't need to explicitly know the pumping length $p$, but just assume it exists. To find $p$ is a different question (and quite interesting one!). As a short and imprecise comment I can say that if you have a grammar $G$ then $p \le |R|$ where $R$ is the set of production rules of that CFG. | |
| Apr 10, 2013 at 5:36 | history | edited | Ran G. | CC BY-SA 3.0 |
latexing, also changing K to p as it is more common.
|
| Apr 10, 2013 at 4:13 | comment | added | Gaak | @LukeMathieson Proving that it is NOT context-free, and I need help to determine the pumping length K | |
| Apr 10, 2013 at 4:01 | comment | added | Luke Mathieson | Are you trying to prove the language isn't regular, or that it isn't context free? The pumping lemmas for either case are not suitable for proving that a language is regular or context free, just that they *aren't *. | |
| Apr 10, 2013 at 3:14 | history | asked | Gaak | CC BY-SA 3.0 |