Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
If you haven't looked at it yet, Colcombet has a really nice survey on related concepts: – Michaël Cadilhac Jan 12 '14 at 16:27
Thanks @Michaël! – R B Jan 19 '14 at 17:00
up vote 9 down vote accepted

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).

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.