# Justification for the pumping lemma of context free languages

I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those repeated states as many times as you wish.

However for the context free language version I can't seem to come up with the same intuitive understanding for why the lemma holds. My textbook mentions abusing the fact every CFG can be put into Chomsky normal form and then using some properties of binary trees to show productions can be pumped but Im having a hard time following why this would lead to repeated states, let alone two repeated states.

The idea is that a sufficiently long string will have some repeated path along it from root to leaf. This path can be repeated as many times as we wish. The left side and the right side of the tree will be "pumped" and the the characters in the center of the subtree will remain. This is where we get x^n y z^n substring from the pumping lemma. I highly recommend watching the video however, it is explained much better and the visualization helps.
A context-free grammar has a finite number of nonterminals. This means the number of different derivation trees you can generate such that each nonterminal on each path of each tree is different is also finite: if you have $$n$$ nonterminals, then each path longer than $$n$$ will contain at least one nonterminal twice. That means all other derivations have a repeating nonterminal $$A$$ on some path. We can then pump by repeating the path segment from $$A$$ to $$A$$ arbitrarily often. This remains true after we make the grammar proper by removing all unproductive and unreachable nonterminals and cyclic rules.
• It's not only two. All paths longer than $n$ in the proper grammar have at least one repeating nonterminal, and hence, are pumpable (and have already been pumped at least once). All strings generated by such paths are the result of pumping one of the (finite set of) unpumped strings at least once, and that pumping can be repeated arbitrarily often. – reinierpost Nov 5 '18 at 16:58