Variable Repetitions in Pumping Lemma for Context-Free Languages

Question

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in An Introduction to Formal Languages and Automata (5th ed.) by Peter Linz:

Let $L$ be an infinite context-free language. Then there exists some positive integer $m$ such that any $\omega$ $\epsilon$ $L$ with $\lvert \omega \rvert \geq m$ can be decomposed as $w = uvxyz$ with $\vert vxy \rvert \leq m$ and $\vert vy \rvert \geq 1$ such that $uv^ixy^iz \in L$ for all $i=0,1,2,\cdots$

Proof: Consider the language $L - \{\lambda\}$, and assume that we have for it a grammar $G$ without unit-productions or $\lambda$-productions. Since the length of the string on the right side of any production is bounded, say by $k$, the length of the derivation of any $\omega$ $\epsilon$ $L$ must be at least $\lvert \omega \rvert / k$. Therefore, since $L$ is infinite, there exists arbitrarily long derivations and corresponding derivation trees of arbitrary height.

Consider now such a high derivation tree and some sufficiently long path from the root to a leaf. Since the number of variables in $G$ is finite, there must be some variable that repeats on this path, as shown schematically in the following derivation tree:

$S$ has subtree $T_1$ with $u$, subtree $A$, and subtree $T_2$ with $z$ in the first level. $A$ has subtree $T_3$ with $v$, subtree $A$, and subtree $T_4$ with $y$ in the second level. $A$ has the subtree $T_5$ with $x$ in the third level.

Corresponding to the derivation tree, we have the derivation$ S\stackrel{*}{\implies}uAz\stackrel{*}{\implies}uvAyz\stackrel{*}{\implies}uvxyz$ where $u$, $v$, $w$, $y$, $z$ are all strings of terminals. From the above we see that $A\stackrel{*}{\implies}vAy$ and $A\stackrel{*}{\implies}x$, so all the strings $uv^ixy^iz$, $i=0,1,2$ can be generated by the grammar and are therefore in $L$.

Furthermore, in the derivations $A\stackrel{*}{\implies}vAy$ and $A\stackrel{*}{\implies}x$, we can assume that no variable repeats. To see this, look at the sketch of the derivation tree. In the subtree $T_5$ no variable repeats; otherwise we could just apply the argument to this repeating variable. Similarly, we can assume no variable repeats in the subtrees $T_3$ and $T_4$.

Therefore, the lengths of the strings $v$, $x$, and $y$ depend only on the productions of the grammar and can be bounded independently of $w$ such that $\vert vxy \rvert \leq m$ holds. Finally, since there are no unit-productions and no $\lambda$-productions, $v$ and $y$ cannot both be empty strings, giving $\vert vy \rvert \geq 1$.

I do not understand two things about this proof:

1. "We can assume that no variable repeats in the subtree $T_5$". Why should there not be any variable that repeats itself? Why is that a problem?

2. "Similarly, we can assume that no variable repeats in the subtrees $T_3$ and $T_4$." I don't quite see how we can fix the issue if there are variables that repeat in the subtrees $T_3$ or $T_4$?

Answer 1

It is certainly possible that some variables repeat in the subtree $T_3$, $T_4$ or $T_5$. There is nothing wrong with those situations, except that those situations are too relaxed for us to ensure "the lengths of the strings $v$, $x$, and $y$ depend only on the productions of the grammar and can be bounded independently of $w$ so that (8.2) holds"

---

Let us verify that we are able to assume those two assumptions.

One way to enable those two assumptions is described in the textbook. I will let you to convince yourself it works.

Here is a slightly different way to enable those two assumptions. We know that there are repeated variables on some path from the root to a leaf. Choose a pair of the same variable so that the number of nodes in the subtree rooted at the upper appearance of the variable is the smallest among all possible such pairs. Let that pair be shown as the two $A$s in the following derivation, which corresponds to figure 8.1.

$$ S\stackrel{*}{\implies}uAz\stackrel{*}{\implies}uvAyz\stackrel{*}{\implies}uvxyz$$

There is no repeated variable in subtrees $T_3$, $T_4$ and $T_5$, since any repeated variable in $T_3$, $T_4$ or $T_5$, say $B$, means the subtree rooted at the upper appearance of $B$ has smaller number of nodes than the subtree rooted at the upper $A$ (as the former tree is strictly contained in the latter tree), which contradicts to how $A$s in the figure have been selected.

---

That means any path from the upper $A$ to any leaf in the tree passes at most $|V|+2$ nodes, where $V$ is the set of variables. ("$+2$" since $A$ may appear twice in that path and the leaf node holds a terminal symbol instead a variable') Since each node can have at most $\ell$ children, where $\ell$ is the maximum length of the string on the right side of any production, the number of leaves in the subtree rooted at the upper $A$ is at most $\ell^{|V|+1}$, i.e., $|vxy|\le\ell^{|V|+1}$. Note $\ell^{|V|+1}$ is a constant that depends on the grammar only.