Ambiguity in Finite Automata
Erik M. Schmidt · DAIMI Report Series · 1977
The gain in succinctness of descriptions of regular languages when nondeterministic (unambiguous) finite automata are used rather than unambiguous (deterministic) finite automata, is not bounded by any polynomium. The problem of deciding whether an unambiguous regular expression does not generate all words over its terminal alphabet, is in NP.