We develop a unified proof technique to study the 0Lness problem (i.e., given a language descriptor, does it generate a 0L language?) across various classes of language descriptors. Notably, we show that the 0Lness problem for linear context-free grammars is productive (a stronger form of non-recursively enumerable), and that it is Co-NEXPTIME-hard for context-free grammars generating finite languages and PSPACE-hard for \(\varvec{(\cup , \cdot , *)}\) -regular expressions. Various decision problems concerning E0L, EDT0L, and ET0L systems are also investigated. These problems include a variety of equivalence and containment problems, and language class comparison problems (e.g., given an arbitrary context-free grammar, does it generate a 0L, DT0L, or EDT0L language?). Most of our results are applicable to promise problems. For example, we show that for a polynomial-time decidable subset of EDT0L systems whose elements only generate regular languages, determining if an element generates a language equal to a fixed unbounded regular set is productive. Analogues of Rice’s theorem for E0L, EDT0L, and ET0L systems are developed. We establish that many predicates are either productive or PSPACE-hard for EDT0L and ET0L systems, and either productive or Co-NP-hard for E0L systems.
