Here’s a CNF (Chomsky normal form) grammar:

S à BC | a
B à BS | b
C à c

•  S Þ* bSc Þ bac
•  but if, instead of rewriting S as “a”
•  we rewrite it as bSc we get S Þ* bbScc Þ bbacc
•  and, repeating n times, we get S Þ* bⁿScⁿ Þ bⁿacⁿ
•  we can pump bac to bⁿacⁿ for any n!
•  and it is the fact that  S Þ* bSc that allows this
•  … we say that S is self-embedding
•  we can always pump for a grammar that has a self-embedded non-terminal, BUT
•  can we pump for all CFG’s?  i.e.
•  do all CFG’s have self-embedded non-terminals?

For the purposes of discussion in this section, we will ignore the leaf nodes of our derivation trees.

Under this assumption, notice that the derivation tree for a CNF CFG is a binary tree.

You can see that the depth of the tree is related to the size of the string that can be derived. A tree of depth 2 (shown above) can produce a sentence of length at most 2² = 4. In general, a derivation tree of depth p can produce a sentence of at most 2^p characters.

Note that not every derivation tree is a complete tree, for which every path from the root to a leaf is the depth of the tree. For the tree shown just above, every path is of length 2. Referring back to the derivation tree shown at the beginning, we observe paths (not including the leaves) of length 2 and 1.

Let’s suppose that our CNG CFG has p productions of the form A à BC, called live productions (as opposed to the other kind, of the form A à a, called dead productions).

Let’s also suppose that we can derive a string of length greater than 2^p.  Can all the paths be of
length <= p?  No!  we have already shown that a derivation tree of depth p can produce a sentence of at most 2^p characters!

So there is at least one path of length > p. How many live productions were used in the course of following that path? Looking at our example, and the highlighted path of length 3:

we see that 3 live productions were used (same as path length).

So for that path of length > p, more than p live productions were used.

If more than p live productions were used in a path (remember, there are only p of them), then some live production A à BC was repeated, and self-embedding of A has occurred! So we have something like that tree shown above, where S à BC was repeated, resulting in the self-embedding of S.

If the production A à BC is repeated along a path, then we have

Notice also (by substitution of A Þ * vAx) we have:

• u and y could be empty
• v and x cannot both be empty, otherwise A Þ* A (in one or more steps) …
• impossible … no l -productions!
• w is not empty … same reason

Here is what we have found:

If a grammar G has p live productions and can generate a string z of length > 2^p, then z = uvwxy, where v and x are not both empty, and the strings uvⁿwxⁿy (n = 2, 3, …) are also generated by G.

The pumping lemma is useful in proving that certain languages are not context free.

Let’s assume that aⁿbⁿcⁿ is generated by a CNF CFG, and that the number of live productions is p. We can certainly generate a string of length > 2^p. By the pumping lemma, it can be written in the form uvwxy, where uv²wx²y is also in the language, and v and x are not both empty.

Proof part 1: If v is non-empty, it cannot be a mixture of letters, e.g. aabb, because then uv²wx²y = u(aabb)²wx²y = uaabbaabbwx²y and would hence not be in the language. Similarly for x.

Proof part 2: v and x cannot be non-mixed letter strings, because, e.g., if v = aaaa, and x = bbbb, then uv²wx²y would have 4 more a’s and b’s, but no more c’s, and would hence not be in the language.