1
$\begingroup$

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$?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .