Abstract A pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C is often used to show particular languages are not in $$\varvec{\mathcal {C}}$$ C . In contrast, we show that a pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C can be used to study the computational complexity of the predicate “ $$\in \varvec{\mathcal {C}}$$ ∈ C ” via highly efficient many-one reductions. In this paper, we use extended regular expressions (EXREGs, introduced in Câmpeanu et al. (Int. J. Foundations Comput. Sci. 14(6), 1007–1018, 2003)) as an example to illustrate the proof technique and establish the complexity of the predicate “is an EXREG language” for several classes of languages. Due to the efficiency of the reductions, both productiveness (a stronger form of non-recursive enumerability) and complexity results can be obtained simultaneously. For example, we show that the predicate “is an EXREG language” is productive (hence, not recursively enumerable) for context-free grammars, and is Co-NEXPTIME-hard for context-free grammars generating bounded languages. The proof technique is easy to use and requires only a few conditions. This suggests that for any class of languages $$\varvec{\mathcal {C}}$$ C having a pumping lemma, the language class comparison problems (e.g., does a given context-free grammar generate a language in $$\varvec{\mathcal {C}}$$ C ?) are almost guaranteed to be hard. So, pumping lemmas sometimes could be “harmful” when studying computational complexity results.

Abstract In Freydenberger (Theory Comput Syst 53(2):159–193, 2013. https://doi.org/10.1007/s00224-012-9389-0 ), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31–70, 2003. https://doi.org/10.1007/s00236-002-0099-y )]. Therefore, the widely discussed predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either $$\{0, 1\}^*$$ { 0 , 1 } ∗ or $$\{0, 1\}^* -\{w\}$$ { 0 , 1 } ∗ - { w } where $$w \in \{0, 1\}^*$$ w ∈ { 0 , 1 } ∗ , the predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established.