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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Apr 10, 2013 at 4:01
  • $\begingroup$ @LukeMathieson Proving that it is NOT context-free, and I need help to determine the pumping length K $\endgroup$
    – Gaak
    Commented Apr 10, 2013 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.
    Commented Apr 10, 2013 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
    Commented Apr 10, 2013 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
    Commented Apr 10, 2013 at 9:00

1 Answer 1

Reset to default
3
$\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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think we have to restrict ourselves w.l.o.g. to chain- and $\varepsilon$-free CFGs, as does the proof (?). $\endgroup$
    – Raphael
    Commented Apr 12, 2013 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
    Commented Apr 13, 2013 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
    Commented Apr 13, 2013 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
    Commented Apr 14, 2013 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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