The pumping lemma for context-free languages

Choose a CNF grammar $G^{\mathrm{\prime }}=(V,\mathrm{\Sigma },P,S)$ with $L(G^{\mathrm{\prime }})=L$ by [L1] and [L2], and let $m:=\mathrm{\mid }V\mathrm{\mid }$. Set $p:=2^{m+1}+1$. Let $z\in L$ satisfy $\mathrm{\mid }z\mathrm{\mid }\ge p$. By [L3], $z$ is the yield of some parse tree $T$ for $G^{\mathrm{\prime }}$. If every root-to-leaf path of $T$ had at most $m$ variable nodes, then $T$ would have height at most $m+1$, so [L4] would give $\mathrm{\mid }z\mathrm{\mid }\le 2^m<p$, contradicting $\mathrm{\mid }z\mathrm{\mid }\ge p$. Therefore some root-to-leaf path has at least $m+1$ variable occurrences.

Choose two equal variables $A$ on the last $m+1$ variable occurrences of such a path, with the upper one above the lower one. Let the yield of the upper $A$-subtree be $vwx$ and the yield of the lower $A$-subtree be $w$, so the whole word is $uvwxy$. Because the lower occurrence lies strictly below the upper one and $G^{\mathrm{\prime }}$ is in CNF, the path segment from the upper $A$ to the lower one cannot consist only of unit moves, so at least one of the side contexts $v$ and $x$ is nonempty. Hence $\mathrm{\mid }vx\mathrm{\mid }\ge 1$. The upper $A$-subtree contains at most the last $m+1$ variable occurrences on the path, so its height is at most $m+2$; therefore [L4] gives $\mathrm{\mid }vwx\mathrm{\mid }\le 2^{m+1}<p$.

The parse-tree segment from the upper occurrence of $A$ down to the lower one shows that $A{\Rightarrow }^{\ast }vAx$, and the lower subtree shows $A{\Rightarrow }^{\ast }w$. Repeating or deleting the first derivation segment any number of times while keeping the rest of the tree fixed yields derivations of $u{v}^{i}w{x}^{i}y$ in $G^{\mathrm{\prime }}$ for every $i\ge 0$. Hence every such word lies in $L(G^{\mathrm{\prime }})=L$.

Therefore the integer $p$ satisfies the required pumping property.