Theorem: Let $G$ be a CFG in Chomsky normal form with $b$ variables. If $G$ generates a string under a derivation of $2^b$ or more steps, then $L(G)$ is infinite.

---

Proof: Note from 2.26, any derivation in a CNF grammar has odd length, so suppose $G$ generates some string $x$ with a derivation of at least $2^b + 1$ steps. Then, also from 2.26, it must be that $\abs{x} \geq 2^{b-1} + 1$. That is, to generate $x$, we must first generate a string containing at least $2^{b-1} + 1$ variables. Write $X$ to denote this final string containing only variables that will then generate $x$.

The parse tree for the derivation of $X$ is strictly a binary tree, because $G$ is CNF, and $X$ consists only of variables. There are (at least) $l = 2^{b-1} + 1$ leaf nodes on this tree. Note that necessarily, the tree is full because every node has either 0 or 2 children. The height of the tree is minimal (that is, can be bounded below) if it also balanced. In that case, the height of a full, balanced binary tree is $h = \lceil \log_2(l) \rceil + 1$. We have that:

$$h = \lceil \log_2(2^{b-1} + 1) \rceil + 1 > \log_2(2^{b-1}) + 1 = (b-1) + 1 = b$$

So $h$ is strictly greater than $b$, which means $h \geq b+1$.

But, if the height is greater than $b$, then by the pigeonhole principle we can conclude that in any particular path (walk) from the root node to a leaf node, we will encounter a repeated variable. That is, there's some variable $A$ such that $A$ can derive another string containing $A$. In other words, $A \Rightarrow^* PAQ$ where $P, Q$ are strings of variables. Then, in particular, $PAQ \Rightarrow^* PPAQQ \Rightarrow^* PPPAQQQ \dots$, which is an infinite family of variable strings that can be generated by $G$, and thus an infinite family of strings in $L(G)$, which makes $L(G)$ infinite.