# How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).

A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path.

This means $DFA\subset UFA\subset NFA$.

Known related automaton results:

1. NFA minimization is PSPACE-Complete.
2. NFA minimization over finite languages is DP-Hard.
3. UFA minimization is NP-Complete.
4. There exists NFAs which are exponentially smaller than minimal DFAs. (Also - there exists UFAs which are exponentially smaller than minimal DFAs - R B).

The question is: can we find a regular language $L$ such that the there exists a NFA accepting $L$ which is exponentially smaller (state-wise) than the minimal UFA for $L$? Can this happen for a finite language?

I believe such (finite) $L$ exists, but my proof currently relies on the Exponential Time Hypothesis to hold, and was wondering if someone has a proof which doesn't rely on it.

Also, can someone characterize the set of languages for which such size difference exist?

EDIT: @Shaull gave a nice link to a paper dealing with infinite language. Does anyone know a similar result for a finite language?