The Pumping Lemma for Context-Free Languages is Undecidable

Recently, the computational complexity of the Pumping-Problem, that is, for a given finite automaton A and a value p, deciding whether the language L(A) satisfies a previously fixed regular pumping lemma w.r.t. the value p, was considered in [H. Gruber and M. Holzer and C. Rauch. The Pumping Lemma for Regular Languages is Hard. CIAA 2023, pp. 128-140.]. Here we generalize the Pumping-Problem by investigating Bar-Hillel’s context-free pumping lemma instead. It turns out that for context-free languages, the Pumping-Problem for Bar-Hillel’s pumping lemma is undecidable. When restricted to regular languages, the problem under consideration becomes decidable.