<p>There is even a stronger result than your request:</p>

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

<p>Check <a href="http://dl.acm.org/citation.cfm?id=284965">this paper</a> by Hing Leung.</p>

CC BY-SA 3.0
2014-01-12T15:41:51.447Z
Thanks @Shaull.

Do you know if a similar result exists for finite languages?
R B
CC BY-SA 3.0
2014-01-12T15:44:34.467Z
I am not aware of any similar results for finite languages, sorry.
Shaull
CC BY-SA 3.0
2014-01-12T15:22:26.647Z
2014-01-12T15:22:26.647Z
Shaull
<p>I think the IJFCS'05 paper by Leung: <a href="http://www.worldscientific.com/doi/pdf/10.1142/S0129054105003418" rel="noreferrer">Descriptional complexity of nfa of different ambiguity</a>
provides an example with a family of NFA accepting finite languages that involve an exponential blowup for "disambiguation" (in the proof of Theorem 5).</p>

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

CC BY-SA 3.0
2014-01-13T13:31:29.827Z
2017-09-27T09:10:57.857Z
2017-09-27T09:10:57.857Z
Joseph Stack
<p>Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).</p>

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

<p>This means $DFA\subset UFA\subset NFA$.</p>

<p>Known related automaton results:</p>

<blockquote>
  <ol>
  <li>NFA minimization is PSPACE-Complete.</li>
  <li><a href="http://www2.tcs.ifi.lmu.de/~gruberh/data/lata07-submission.pdf" rel="nofollow noreferrer">NFA minimization over finite languages is DP-Hard</a>.</li>
  <li><a href="http://lrb.cs.uni-dortmund.de/~martens/data/icalp08talk.pdf" rel="nofollow noreferrer">UFA minimization is NP-Complete</a>.</li>
  <li><a href="https://cs.stackexchange.com/questions/3381/nfa-with-exponential-number-of-states-when-deteminized">There exists NFAs which are exponentially smaller than minimal DFAs</a>.
  (Also - there exists UFAs which are exponentially smaller than minimal DFAs - R B).</li>
  </ol>
</blockquote>

<p>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 <strong>UFA</strong> for $L$?
Can this happen for a finite language?</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2014-01-12T16:27:06.707Z
If you haven't looked at it yet, Colcombet has a really nice survey on related concepts: http://www.liafa.jussieu.fr/~colcombe/Publications/STACS12-colcombet.pdf
Michaël Cadilhac
<cc.complexity-theory><fl.formal-languages><automata-theory><regular-language>
How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?
R B
# How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

(Asked by: username_0 on 2014-01-12)

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](http://www2.tcs.ifi.lmu.de/~gruberh/data/lata07-submission.pdf).
> 3. [UFA minimization is NP-Complete](http://lrb.cs.uni-dortmund.de/~martens/data/icalp08talk.pdf).
> 4. [There exists NFAs which are exponentially smaller than minimal DFAs](https://cs.stackexchange.com/questions/3381/nfa-with-exponential-number-of-states-when-deteminized).
>    (Also - there exists UFAs which are exponentially smaller than minimal DFAs - username_0).

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: @username_2 gave a nice link to a paper dealing with infinite language. Does anyone know a similar result for a finite language?

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, regular-language

> **Comments:**
> **username_1**: If you haven't looked at it yet, Colcombet has a really nice survey on related concepts: http://www.liafa.jussieu.fr/~colcombe/Publications/STACS12-colcombet.pdf  

---

## 2 answers

### Answer by username_3 on 2014-01-13. Score: 14 | Accepted answer

I think the IJFCS'05 paper by Leung: [Descriptional complexity of nfa of different ambiguity](http://www.worldscientific.com/doi/pdf/10.1142/S0129054105003418)
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).


---

### Answer by username_2 on 2014-01-12. Score: 17

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](http://dl.acm.org/citation.cfm?id=284965) by Hing Leung.

> **Comments:**
> **username_0**: Thanks @username_2.  Do you know if a similar result exists for finite languages?  
> **username_2**: I am not aware of any similar results for finite languages, sorry.  

---

