The Pumping Lemma for Regular Languages is Hard
Hermann Gruber, Markus Holzer, Christian Rauch · International Journal of Foundations of Computer Science · 2025
We investigate the computational complexity of the Pumping-Problem, that is, for a given finite automaton A and a value p, to decide whether the language [Formula: see text] satisfies a previously fixed pumping lemma w.r.t. the value p. Here we concentrate on two different pumping lemmata from the literature. It turns out that this problem is intractable, namely, it is already coNP -complete, even for deterministic finite automata (DFAs), and it becomes PSPACE -complete for nondeterministic finite state devices (NFAs), for at least one of the considered pumping lemmata. In addition, we show that the minimal pumping constant for the considered pumping lemmata cannot be approximated within a factor of [Formula: see text] with [Formula: see text], for a given n-state NFA, unless the Exponential Time Hypothesis (ETH) fails.