Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata

We resolve an open problem raised by Ravikumar and Ibarra [SIAM J. Comput., 18 (1989), pp. 1263--1282] on the succinctness of representations relating to the types of ambiguity of finite automata. We show that there exists a family of nondeterministic finite automata {A n } over a two-letter alphabet such that, for any positive integer n, A n is exponentially ambiguous and has n states, whereas the smallest equivalent deterministic finite automaton has 2 n states, and any smallest equivalent polynomially ambiguous finite automaton has 2 n -1 states.