Georg Zetzsche

@Raphael $P$ from the context-free is decidable: P(g,w,d) then says "d encodes a derivation tree for w in which a nonterminal repeats". For a suitable encoding, that is decidable.

Do you have an example of a pumping lemma that does not meet the conditions in my answer? Or do you know one where this is not clear?

If your point is that not everything that fits this definition of a pumping lemma is in fact a pumping lemma: That might very well be. The notion is is purposefully made extremely weak.

Think of the $d$ as a certificate that one can derive infinitely many words (a run with repeated states; a derivation tree with a branch repeating a letter etc.). And the decidability of P means one can verify that this is a certificate.

Take the NFA example I added in the text--Only sufficiently long $w$ admit a $d$.

@Raphael The $d$ serves as a witness for infinity. Not every $w$ has a $d$ such that $P(g,w,d)$:

@Raphael This notion captures the classical pumping lemmas. I made the NFA example explicit; does it make sense now?

@Raphael The definition tries to be as weak as possible. It just requires the existence of an infinite subset of $L(g)$ (you can call that set $L_{\text{pump}}$ if you like). It does not say anything about how these words are constructed. Note that this makes the notion of "pumping lemma" weaker and hence the non-existence stronger.

@Raphael I want it to be g to make the notion as weak as possible. Note that this merely requires that our language is infinite. Maybe there was a misunderstanding, I made the answer a bit clearer.