Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)

Question

Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$

Answer 1

If the derivation has atleast ${2^b}$ derivations , then since the grammar is in Chomsky Normal Form, then the length of the string is atleast ${2^b}$ $\Rightarrow$ the height of the tree is atleast b+1. Now from the Proof of Pumping Lemma(Not in Sipser, but in Hopcroft-Ullman) you can find that we can pump any number of strings , i.e the language is infinite.