  The ambiguity of a nondeterministic finite automaton (NFA) N for input size n
is the maximal number of accepting computations of N for an input of size n.
For all k, r 2 N we construct languages Lr,k which can be recognized by NFA's
with size k poly(r) and ambiguity O(nk), but Lr,k has only NFA's with
exponential size, if ambiguity o(nk) is required. In particular, a hierarchy
for polynomial ambiguity is obtained, solving a long standing open problem
(Ravikumar and Ibarra, 1989, Leung, 1998).
