The Pumping Lemma for Regular Languages is Hard

We investigate the computational complexity of the Pumping-Problem, that is, for a given finite automaton [Formula: see text] and a value [Formula: see text], to decide whether the language [Formula: see text] satisfies a previously fixed pumping lemma w.r.t. the value [Formula: see text]. 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 [Formula: see text]-state NFA, unless the Exponential Time Hypothesis (ETH) fails.