  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 $\ell \geq 0$ such that $\Sigma^\ell \subseteq
L(M)$? In the case of an NFA, we show that this problem is NEXPTIME-complete,
and the smallest such $\ell$ 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 $\ell$ 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^{\sqrt{n \log n}
(1+o(1))}$ is an asymptotically tight upper bound for the smallest such $\ell$,
where $n$ is the number of states. Finally, we prove that in all these cases,
the problem becomes computationally easier when the length $\ell$ 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.
