On the degree of ambiguity of finite automata

We investigate the ambiguity behavior of finite automata in connection with their inner structure. We show that the degree of ambiguity of a finitely ambiguous nondeterministic finite automaton (NFA) with n states is at most 5 ^{n 2}·nⁿ. There is a simple criterion which characterizes the infinite degree of ambiguity of an NFA, and which is decidable in polynomial time. The degree of growth of the ambiguity of an NFA is computable in polynomial time. Starting from the first result, we discuss the maximal finite degree of ambiguity of an NFA with n states, and we present subclasses of NFAs where this quantity is of order 2^Θ(n).