摘要：We study the following natural variation on the classical universality problem: given a language L(M) represented by M (e.g., a DFA/RE/NFA/PDA), does there exist an integer ð" ⥠0 such that Σ^ð" âS L(M)? In the case of an NFA, we show that this problem is NEXPTIME-complete, and the smallest such ð" can be doubly exponential in the number of states. This particular case was formulated as an open problem in 2009, and our solution uses a novel and involved construction. In the case of a PDA, we show that it is recursively unsolvable, while the smallest such ð" is not bounded by any computable function of the number of states. In the case of a DFA, we show that the problem is NP-complete, and e^{â^S{n log n} (1+o(1))} is an asymptotically tight upper bound for the smallest such ð", where n is the number of states. Finally, we prove that in all these cases, the problem becomes computationally easier when the length ð" is also given in binary in the input: it is polynomially solvable for a DFA, PSPACE-complete for an NFA, and co-NEXPTIME-complete for a PDA.
