There are variants of the pumping lemma. I will use yours.
Note that you have really 3 length conditions. The missing one is
about the minimum total length of the word. I treat it with the second
In a (big) nutshell :
I call subtree any subpart of the parse tree that has at most one
non-terminal at the fringe. The pumping lemma uses recursive subtrees
where the non terminal in the fringe is the same as the root of the
subtree. The whole parse tree is a subtree.
Subtrees as defined here (and recursive subtrees) are the heart of the matter. Their existence is directly related to the context-freeness.
1st condition: it states simply that if there is an unproductive
(fringe with no termina symbol) recursive subtree in the parse tree, it can be
short-circuited, so that we are always sure the fringe contains a
A finiteness issue: It will be used twice. If you have a
subtree that contains no recursive subtree, then no path in the
subtree has twice the same label (subtree root excepted). The subtree
is finitely branching with a limited depth (no more than the
number of non-terminals).Hence you have a finite set of such subtrees
generating only a finite set of strings at their fringe. Being finite
in number, there is an upperbound for the length of the fringes. A contrario, if a fringe exceeds the bound, it is a sure indication it contains a recursive subtree.
The "missing condition" that $\mid s\mid \geq p$ ensure that the
string is long enough so that there
is at least one recursive subtree in the parse tree for pumping.
2nd condition: you can always get for pumping a
recursive subtree that neither dominate nor contains another recursive
subtree in the parse tree. If it does, just take the other recursive
subtree. Since the parse tree is finite, this terminates. You end up
with subtrees (for $vy$ and for $x$) that do not contain recursive
subtrees, and the finiteness analysis above garantees the existence of
In the regular grammar case you just have subtrees that do not branch
very much. It is really identical to the CF case with some strings
replaced by $\epsilon$.
In the CF case, it is often convenient for the proof of the lemma, or
its variations, to assume that the grammar is CNF (depending also on
the lemma variant)
Much of the formal proof is mathematical presentation, not understanding.
This was an interesting exercise.