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

Question

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?

Answer 1

There is even a stronger result than your request:

There are exponentially-ambiguous NFAs for which the minimal polynomially-ambiguous NFAs are exponentially larger, and in particular the minimal UFAs.

Check this paper by Hing Leung.

Answer 2

I think the IJFCS'05 paper by Leung: Descriptional complexity of nfa of different ambiguity provides an example with a family of NFA accepting finite languages that involve an exponential blowup for "disambiguation" (in the proof of Theorem 5).

What is more, those automata have a special structure (DFA with multiple initial states).