I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows:

If $A$ is a context-free language, then there exists a number $p$ (the pumping length) where, if $s$ is any string in $A$ whose length is at least $p$, then $s$ can be divided into five parts $s = uvxyz$ satisfying the conditions:

  1. for every $i\geq 0$, $uv^ixy^iz \in A$,
  2. $|vy|>0$, and
  3. $|vxy| \leq p$

The proof is as follows:

Let $G$ be a context-free grammar for the context-free language $A$. Let $b$ be the maximum number of symbols on the right side of a rule. Thus, in any syntactic tree using this grammar, a node can have at most $b$ children. Therefore, if the height of the syntactic tree is at most $h$, the pumping length of the generated string is at most $b^h$. Reciprocally, if a generated string has length at least $b^h+1$, each of its syntactic trees must have a height of at least $h+1$.

Let $|V|$ be the number of variables (non-terminal symbols) of $G$. Let $p$, the pumping length, be $b^{|V|} + 1$. Now, if $s$ is a string in $A$ and its length is $p$ or more, its syntactic tree must have a height of at least $|V|+1$.

To see how to pump any of these strings $s$, let $\tau$ be one of its syntactic trees which has the least number of nodes. We know that $\tau$ has height, at least, $|V|+1$, therefore it must contain a path from the root to a leaf of length at least $|V|+1$. This path has at least $|V|+2$ nodes, one in a terminal symbol and the other ones in variables. So, this path has at least $|V|+1$ variables. By the pigeonhole principle, some variable $R$ appears more than once in this path. Let $R$ be a variable that repeats among the $|V|+1$ lowest variables in this path.

Then, the proofs for conditions 1, 2 and 3 are shown. I won't transcribe the proofs for condition 1 and 2, because I understood them. My problem is with condition 3:

To obtain condition 3, we have to be sure that $vxy$ has length at most $p$. In the syntactic tree for $s$, the upper occurrence of $R$ generates $vxy$. We chose $R$ such that both occurrences are among the $|V|+1$ lower variables in the path, and we chose the longest path in the tree, so the subtree where $R$ generates $vxy$ has height at most $|V|+1$. A tree with this height can generate a string of length at most $b^{|V|+1} = p$.

I'm confused about the last paragraph. Initially, it chooses the pumping length to be $b^{|V|} + 1$, and it concludes that the height of every syntatic tree of $s$ with $|s| \geq p$ is at most $|V|+1$. However, afterwards, it concludes that, since the subtree where $R$ generates $vxy$ has height at most $|V| + 1$, the string generated by this subtree has length at most $b^{|V|+1} = p$. But isn't $p = b^{|V|}+1$?


There does appear to be an error in the argument. It can be fixed by taking $p$ initially to be $b^{|V|+1}$: we may assume that $b>1$ (as otherwise the language is finite and therefore regular), so $b^{|V|+1}\ge 2b^{|V|}\ge b^{|V|}+1$, and we can still argue that a syntactic tree for $s$ must have height at least $|V|+1$.


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.