4
$\begingroup$

Please help me understand, and if possible, tips, to determine a pumping length $p$.

Suppose I have the example :

Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of terminals $\{0,1\}$, start variable $S$, and rules

$S \to ABA \mid SS$
$A \to S0 \mid 1C1$
$B \to S1 \mid 0$
$C \to 0$

Now given the above, how do I find the pumping length $p$?
Please explain how you actually got it from the grammar.

$\endgroup$
  • $\begingroup$ 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 *. $\endgroup$ – Luke Mathieson Apr 10 '13 at 4:01
  • $\begingroup$ @LukeMathieson Proving that it is NOT context-free, and I need help to determine the pumping length K $\endgroup$ – Gaak Apr 10 '13 at 4:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Ran G. Apr 10 '13 at 5:44
  • 1
    $\begingroup$ @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". $\endgroup$ – Yuval Filmus Apr 10 '13 at 6:25
  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 10 '13 at 9:00
2
$\begingroup$

As Raphael says in the comments, any sufficiently large number is suitable as a pumping length, however (also as he points out), the proof of the pumping lemma gives an upper bound for the minimum pumping length.

Similar to the pumping lemma for regular languages, we want to take a length that is sufficiently large that we can guarantee that we have used the same production at least twice. For regular languages this often easy to think of as the number states in a minimal DFA for that language.

For context free languages expressed with a grammar, we can take a similar approach and ask "how many symbols can be in the string before I know that I must have used some production twice?". To figure this out you may want to consider how many symbols any production could insert into the string, and what the parse tree for a sufficiently long string may look like (you can consider each level of the tree to be one production). If you do this correctly you can get a minimal pumping length for that grammar (not exactly a precise concept), then taking the minimum of these minimal lengths over all grammars for the language will give you the minimum for the language.

Further hint:

If there's a rule with $m$ symbols on the right hand side, and the parse tree is $d$ levels deep, what's the maximum number of symbols in the string?

$\endgroup$
  • $\begingroup$ I think we have to restrict ourselves w.l.o.g. to chain- and $\varepsilon$-free CFGs, as does the proof (?). $\endgroup$ – Raphael Apr 12 '13 at 13:20
  • $\begingroup$ @Raphael not the ones I have here (Sipser and Kinber & Smith), you only need that a long enough terminal string guarantees that the parse tree has a minimum depth. $\endgroup$ – Luke Mathieson Apr 13 '13 at 1:46
  • 1
    $\begingroup$ I think cycles generating $\varepsilon$ have to be avoided, since those can not be pumped to generate longer words. If I remember correctly, the proofs I have seen use Chomsky normal form which does not have that problem. $\endgroup$ – Raphael Apr 13 '13 at 13:03
  • $\begingroup$ Ah, the proofs "here" implicitly avoid that by starting with a lemma that any string of length at least $p=w^{d}$ has a parse tree of depth at least $d$ where $w$ is the maximum number of symbols on right of a production - so any productions that lead to $\varepsilon$ don't add to the length $p$, effectively restricting our interest to paths that actually produce a non-$\varepsilon$ character. $\endgroup$ – Luke Mathieson Apr 14 '13 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.