On Jaffe's pumping lemma, revisited

We consider Jaffe's pumping lemma [ J. Jaffe . A necessary and sufficient pumping lemma for regular languages. SIGACT News , Summer, 1978] from a descriptional complexity perspective. Jaffe's pumping lemma is a necessary and sufficient condition for a language for being regular. Building on this, we improve on a result of [ A. Yehudai . A note on the pumping lemma for regular languages. Inform. Proc. Lett. , 9(3):135–136, 1979] by proving the existence of a regular language over an alphabet Σ with at least two symbols whose deterministic state complexity lies strictly between p , the minimal pumping constant in Jaffe's lemma, and ∑ i = 0 p − 1 | Σ | i . This finding aligns with recent work on minimal pumping constants for various pumping lemmas, as studied in [ J. Dassow and I. Jecker . Operational complexity and pumping lemmas. Acta Inform. , 59:337–355, 2022]. We further compare the minimal pumping constant in Jaffe's lemma with those of other well-known pumping lemmata from the literature, demonstrating that, in most cases, these constants can be independently assigned across the different lemmata.