# 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?

-
If you haven't looked at it yet, Colcombet has a really nice survey on related concepts: liafa.jussieu.fr/~colcombe/Publications/STACS12-colcombet.pdf – Michaël Cadilhac Jan 12 '14 at 16:27
Thanks @Michaël! – R B Jan 19 '14 at 17:00

I think the IJFCS'05 paper by Leung: Descriptional complexity of nfa of different ambiguity provides an exemple 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).

-
Very nice @Joseph, thanks ! – R B Jan 13 '14 at 16:32

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.

-
Thanks @Shaull. Do you know if a similar result exists for finite languages? – R B Jan 12 '14 at 15:41
I am not aware of any similar results for finite languages, sorry. – Shaull Jan 12 '14 at 15:44