<h2>EDIT AT 10/12/06:</h2>

<p>ok, this is pretty much the best construction I can get, see if any one come up with better ideas.</p>

<blockquote>
  <p><strong>Theorem.</strong> For each $n$ There is an $(5n+12)$-state NFA $M$ over alphabets $\Sigma$ with $|\Sigma|=5$ such that the shortest string not in $L(M)$ is of length $(2^n-1)(n+1)+1$.</p>
</blockquote>

<p>This will give us $f(n) = \Omega(2^{n/5})$.</p>

<p>The construction is pretty much the same with the one in <a href="http://www.cs.uwaterloo.ca/~shallit/Talks/re.ps" rel="nofollow noreferrer">Shallit's</a>, except we construct an NFA directly instead of representing the language by a regular expression first. Let </p>

<p>$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$.</p>

<p>For each $n$, we are going to construct an NFA recognizing language $\Sigma^*-\{s_n\}$, where $s_n$ is the following sequence (take $n=3$ for example):</p>

<p>$s_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$.</p>

<p>The idea is that we can construct an NFA consists of five parts; </p>

<ul>
<li>a <em>starter</em>, which ensures the string starts with $\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$; </li>
<li>a <em>terminator</em>, which ensures the string ends with $\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$;</li>
<li>a <em>counter</em>, which keeps the number of symbols between two $\sharp$'s as $n$;</li>
<li>an <em>add-one checker</em>, which guarantees that only symbols with the form $\sharp{x \atop x+1}\sharp$ appears; finally,</li>
<li>a <em>consistent checker</em>, which guarantees that only symbols with the form $\sharp{x \atop y}\sharp{y \atop z}\sharp$ can appear concurrently.</li>
</ul>

<p>Note that we do want to accept $\Sigma^*-\{s_n\}$ instead of $\{s_n\}$, so once we find out that the input sequence is disobeying one of the above behaviors, we accept the sequence immediately. Otherwise after $|s_n|$ steps, the NFA will be in the only possible rejecting state. And if the sequence is longer than $|s_n|$, the NFA also accepts. So any NFA satisfies the above five conditions will only reject $s_n$.</p>

<p>It may be easy to check the following figure directly instead of a rigorous proof:</p>

<p><img src="https://i.sstatic.net/0lBw0.jpg" alt="NFA for rejecting s_n"></p>

<p>We start at the upper-left state. The first part is the starter, and the counter, then the consistent checker, the terminator, finally the add-one checker. All the arc with no terminal nodes point to the bottom-right state, which is an all time acceptor. Some of the edges are not labeled due to lack of spaces, but they can be recovered easily. A dash line represents a sequence of $n-1$ states with $n-2$ edges.</p>

<p>We can (painfully) verify that the NFA rejects $s_n$ only, since it follows all the five rules above. So a $(5n+12)$-state NFA with $|\Sigma|=5$ has been constructed, which satisfies the requirement of the theorem.</p>

<p>If there's any unclearliness/problem with the construction, please leave a comment and I'll try to explain/fix it.</p>

<hr>

<p>This question has been studied by <a href="http://www.cs.uwaterloo.ca/~shallit/" rel="nofollow noreferrer">Jeffrey O. Shallit</a> et al., and indeed the optimal value of $f(n)$ is still open for $|\Sigma|&gt;1$. (As for unary language, see the comments in <a href="https://cstheory.stackexchange.com/questions/3496/conditions-for-nfa-universality/3502#3502">Tsuyoshi's answer</a>) </p>

<p>In page 46-51 of <a href="http://www.cs.uwaterloo.ca/~shallit/Talks/re.ps" rel="nofollow noreferrer">his talk on universality</a>, he provided a construction such that:</p>

<blockquote>
  <p><strong>Theorem.</strong> For $n\geq N$ for some $N$ large enough, there is an $n$-state NFA $M$ over binary alphabets such that the shortest string not in $L(M)$ is of length $\Omega(2^{cn})$ for $c=1/75$.</p>
</blockquote>

<p>Thus the optimal value for $f(n)$ is somewhere between $2^{n/75}$ and $2^n$. I'm not sure if the result by Shallit has been improved in recent years.</p>

CC BY-SA 2.5
2010-12-06T04:32:58.877Z
I'm playing with Shallit's work, hope to get a better bound much near $2^n$. Their construction seems interesting, by specify some sequence of length $\hat{\Omega}(2^n)$ which can not be represent by a "short" regular expression of length $cn+o(n)$, and each regular expression of length $f(n)$ can be described by an NFA of size $f(n)+1$. Currently I'm able to let $c \leq 22$, but a smarter idea is need to come close $2^n$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-09T19:49:11.417Z
I don't think it gives further insights for studying this problem, but the proper scholarly reference for Shallit's talk is: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)
Hermann Gruber
CC BY-SA 2.5
2010-12-10T00:55:44.693Z
@Hermann: Thank you for the reference, currently I cannot access to the paper, but I will find a way to.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-10T01:26:55.723Z
I think by using *counter* we can replace the *starter* and *terminator* by a 2-state tiny machine. So this further reduce the size of NFA to $3n+O(1)$.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-03-09T21:59:01.413Z
The author's preprint version of the noted JALC paper is here: https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf The bound, and the proof is the same in the printed version.
Hermann Gruber
CC BY-SA 2.5
2010-12-05T15:21:20.383Z
2010-12-06T15:45:57.327Z
2017-04-13T12:32:28.117Z
Hsien-Chih Chang 張顯之
<p>For the statement to hold, <i>f</i> must grow exponentially, even with the unary alphabet.</p>

<p><em>[Edit: The analysis is improved slightly in revision 2.]</em></p>

<p>Here is a proof sketch.  Suppose that the statement holds and let <i>f</i> be a function such that every NFA with at most <i>n</i> states that accepts all strings with length at most <i>f</i>(<i>n</i>) accepts all strings whatsoever.  We will prove that for every <i>C</i>&gt;0 and sufficiently large <i>n</i>, we have <i>f</i>(<i>n</i>) &gt; 2<sup><i>C</i>⋅√<i>n</i></sup>.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a> implies that for every <i>c</i> &lt; lg e and for sufficiently large <i>k</i>, there are at least <i>c</i> ⋅2<sup><i>k</i></sup> / <i>k</i> primes in the range [2<sup><i>k</i></sup>, 2<sup><i>k</i>+1</sup>].  We take <i>c</i>=1.  For such <i>k</i>, let <i>N</i><sub><i>k</i></sub> = ⌈2<sup><i>k</i></sup> / <i>k</i>⌉ and define an NFA <i>M</i><sub><i>k</i></sub> as follows.  Let <i>p</i><sub>1</sub>, …, <i>p</i><sub><i>N</i><sub><i>k</i></sub></sub> be distinct primes in the range [2<sup><i>k</i></sup>, 2<sup><i>k</i>+1</sup>].  The NFA <i>M</i><sub><i>k</i></sub> has <i>S</i><sub><i>k</i></sub>=1+<i>p</i><sub>1</sub>+…+<i>p</i><sub><i>N</i><sub><i>k</i></sub></sub> states.  Apart from the initial state, the states are partitioned into <i>N</i><sub><i>k</i></sub> cycles where the <i>i</i>th cycle has length <i>p</i><sub><i>i</i></sub>.  In each cycle, all but one state are accepted states.  The initial state has <i>N</i><sub><i>k</i></sub> outgoing edges, each of which goes to the state immediately after the rejected state in each cycle.  Finally, the initial state is also accepted.</p>

<p>Let <i>P</i><sub><i>k</i></sub> be the product <i>p</i><sub>1</sub>…<i>p</i><sub><i>N</i><sub><i>k</i></sub></sub>.  It is easy to see that <i>M</i><sub><i>k</i></sub> accepts all strings of length less than <i>P</i><sub><i>k</i></sub> but rejects the string of length <i>P</i><sub><i>k</i></sub>.  Therefore, <i>f</i>(<i>S</i><sub><i>k</i></sub>)≥<i>P</i><sub><i>k</i></sub>.</p>

<p>Note that <i>S</i><sub><i>k</i></sub> ≤ 1 + <i>N</i><sub><i>k</i></sub>⋅2<sup><i>k</i>+1</sup> = o(2<sup>2<i>k</i></sup>) and that <i>P</i><sub><i>k</i></sub> ≥ (2<sup><i>k</i></sup>)<sup><i>N</i><sub><i>k</i></sub></sup> ≥ 2<sup>2<sup><i>k</i></sup></sup>.  The rest is standard.</p>

CC BY-SA 2.5
2010-12-04T18:42:03.153Z
What is your conjecture about the best value of $f$? Say $f(n) = 2^n+1$, or somewhere between $2^n$ and $2^{c\cdot\sqrt{n}}$?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-04T19:22:20.507Z
@Hsien-Chih: I was wondering the same thing, and I do not have any reasonable conjecture.  First, it is trivial to see f(n)≤2^n (we do not need +1) and, while I expect some linear improvement over this upper bound, I have no idea whether it is tight up to a constant factor.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-04T19:23:20.773Z
(cont’d)  Second, as for the lower bound, if I am not mistaken, a slight refinement of the above analysis gives the following lower bound: for every constant 0 < c < $1/\sqrt2$ and sufficiently large n, we have $f(n) > e^{c\sqrt{n \ln n}}$.  Further refinements are probably possible, but we cannot obtain a lower bound such as 2^{n^p} for p>1/2 if we use the same construction of the NTM.  I think that it is an interesting question whether the use of the distribution of primes (such as the PNT) is essential for a construction of bad examples.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-04T19:25:14.673Z
(cont’d)  However, if you are interested and want to investigate it further, probably it is wiser to look for the literature first.  I will not be surprised if this answer or something better has already appeared in the literature.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-04T19:27:59.553Z
Oops, I should have written $f(n) \le 2^n-1$ in my first comment.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-05T11:40:03.090Z
@Tsuyoshi: It is shown by Chrobak that an n-state DFA for an unary language can be simulated by an m-state NFA for $m=O(e^{\sqrt{n\log n}})$. Thus your construction is tight if the language is unary. See [Chr86]: http://www.cs.ust.hk/mjg_lib/Library/Chro86.pdf
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-05T19:20:41.440Z
@Hsien-Chih: Thanks for the reference!  Actually, it seems that it is possible to combine the construction in the paper and the construction in this answer to get a tighter lower bound.  If you or anyone else wants to do this, please feel free to post it as a separate answer.  If no one does this, I will try to update my answer in a few days.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-06T04:34:04.460Z
@Tsuyoshi: Do you mean by combining your answer to [Chr86], or the work by Shallit? I'm pretty amazed if it is the latter case.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-06T04:42:48.030Z
@Hsien-Chih: What I meant was modifying the construction in the proof of Theorem 4.5 in [Chr86] slightly for this problem (“combining” with my answer was an overstatement).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-03T15:45:43.860Z
2010-12-04T18:14:25.487Z
2010-12-04T18:14:25.487Z
Tsuyoshi Ito
<p>Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.</p>

<p>Now lets analyze the following statement:</p>

<blockquote>
  <p>If $\Sigma^{\leq f(|Q|)} \subseteq L(A)$, then $L(A) = \Sigma^*$.</p>
</blockquote>

<p>It is easy to show, that for $f(n) = 2^n+1$ it is true, hence if the automata produces every word with length upto $2^{|Q|}+1$, then it produces $\Sigma^*$.</p>

<p>But does it still hold if $f$ is a polynom?</p>

<p>If not, what could a construction of a NFA $A$ for a given polynom $p$ look like, s.t. $\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$?</p>

CC BY-SA 2.5
2010-12-09T04:51:24.620Z
I would like to give the bounty to a proof or disproof that $f(n)=2^{n−o(n)}$ for the case $|\Sigma|\geq 2$. And if there is none, I'll give it to the best construction one can get.
Hsien-Chih Chang 張顯之
<automata-theory><fl.formal-languages><nondeterminism>
Conditions for NFA universality
Mike B.
# Conditions for NFA universality

(Asked by: username_0 on 2010-12-03)

Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q\_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup\_{i \leq k} \Sigma^i$.

Now lets analyze the following statement:

> If $\Sigma^{\leq f(|Q|)} \subseteq L(A)$, then $L(A) = \Sigma^\*$.

It is easy to show, that for $f(n) = 2^n+1$ it is true, hence if the automata produces every word with length upto $2^{|Q|}+1$, then it produces $\Sigma^\*$.

But does it still hold if $f$ is a polynom?

If not, what could a construction of a NFA $A$ for a given polynom $p$ look like, s.t. $\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^\*$?

**Tags:** automata-theory, fl.formal-languages, nondeterminism

> **Comments:**
> **username_1**: I would like to give the bounty to a proof or disproof that $f(n)=2^{n−o(n)}$ for the case $|\Sigma|\geq 2$. And if there is none, I'll give it to the best construction one can get.  

---

## 2 answers

### Answer by username_3 on 2010-12-03. Score: 22 | Accepted answer

For the statement to hold, *f* must grow exponentially, even with the unary alphabet.

*[Edit: The analysis is improved slightly in revision 2.]*

Here is a proof sketch. Suppose that the statement holds and let *f* be a function such that every NFA with at most *n* states that accepts all strings with length at most *f*(*n*) accepts all strings whatsoever. We will prove that for every *C*>0 and sufficiently large *n*, we have *f*(*n*) > 2*C*⋅√*n*.

The [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem) implies that for every *c* < lg e and for sufficiently large *k*, there are at least *c* ⋅2*k* / *k* primes in the range [2*k*, 2*k*+1]. We take *c*=1. For such *k*, let *N**k* = ⌈2*k* / *k*⌉ and define an NFA *M**k* as follows. Let *p*1, …, *p**N**k* be distinct primes in the range [2*k*, 2*k*+1]. The NFA *M**k* has *S**k*=1+*p*1+…+*p**N**k* states. Apart from the initial state, the states are partitioned into *N**k* cycles where the *i*th cycle has length *p**i*. In each cycle, all but one state are accepted states. The initial state has *N**k* outgoing edges, each of which goes to the state immediately after the rejected state in each cycle. Finally, the initial state is also accepted.

Let *P**k* be the product *p*1…*p**N**k*. It is easy to see that *M**k* accepts all strings of length less than *P**k* but rejects the string of length *P**k*. Therefore, *f*(*S**k*)≥*P**k*.

Note that *S**k* ≤ 1 + *N**k*⋅2*k*+1 = o(22*k*) and that *P**k* ≥ (2*k*)*N**k* ≥ 22*k*. The rest is standard.

> **Comments:**
> **username_1**: What is your conjecture about the best value of $f$? Say $f(n) = 2^n+1$, or somewhere between $2^n$ and $2^{c\cdot\sqrt{n}}$?  
> **username_3**: @Hsien-Chih: I was wondering the same thing, and I do not have any reasonable conjecture.  First, it is trivial to see f(n)≤2^n (we do not need +1) and, while I expect some linear improvement over this upper bound, I have no idea whether it is tight up to a constant factor.  (more)  
> **username_3**: (cont’d)  Second, as for the lower bound, if I am not mistaken, a slight refinement of the above analysis gives the following lower bound: for every constant 0 < c < $1/\sqrt2$ and sufficiently large n, we have $f(n) > e^{c\sqrt{n \ln n}}$.  Further refinements are probably possible, but we cannot obtain a lower bound such as 2^{n^p} for p>1/2 if we use the same construction of the NTM.  I think that it is an interesting question whether the use of the distribution of primes (such as the PNT) is essential for a construction of bad examples.  (more)  
> **username_3**: (cont’d)  However, if you are interested and want to investigate it further, probably it is wiser to look for the literature first.  I will not be surprised if this answer or something better has already appeared in the literature.  
> **username_3**: Oops, I should have written $f(n) \le 2^n-1$ in my first comment.  
> **username_1**: @Tsuyoshi: It is shown by Chrobak that an n-state DFA for an unary language can be simulated by an m-state NFA for $m=O(e^{\sqrt{n\log n}})$. Thus your construction is tight if the language is unary. See [Chr86]: http://www.cs.ust.hk/mjg_lib/Library/Chro86.pdf  
> **username_3**: @Hsien-Chih: Thanks for the reference!  Actually, it seems that it is possible to combine the construction in the paper and the construction in this answer to get a tighter lower bound.  If you or anyone else wants to do this, please feel free to post it as a separate answer.  If no one does this, I will try to update my answer in a few days.  
> **username_1**: @Tsuyoshi: Do you mean by combining your answer to [Chr86], or the work by Shallit? I'm pretty amazed if it is the latter case.  
> **username_3**: @Hsien-Chih: What I meant was modifying the construction in the proof of Theorem 4.5 in [Chr86] slightly for this problem (“combining” with my answer was an overstatement).  

---

### Answer by username_1 on 2010-12-05. Score: 21

## EDIT AT 10/12/06:

ok, this is pretty much the best construction I can get, see if any one come up with better ideas.

> **Theorem.** For each $n$ There is an $(5n+12)$-state NFA $M$ over alphabets $\Sigma$ with $|\Sigma|=5$ such that the shortest string not in $L(M)$ is of length $(2^n-1)(n+1)+1$.

This will give us $f(n) = \Omega(2^{n/5})$.

The construction is pretty much the same with the one in [Shallit's](http://www.cs.uwaterloo.ca/~shallit/Talks/re.ps), except we construct an NFA directly instead of representing the language by a regular expression first. Let

$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$.

For each $n$, we are going to construct an NFA recognizing language $\Sigma^\*-\{s\_n\}$, where $s\_n$ is the following sequence (take $n=3$ for example):

$s\_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$.

The idea is that we can construct an NFA consists of five parts;

* a *starter*, which ensures the string starts with $\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$;
* a *terminator*, which ensures the string ends with $\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$;
* a *counter*, which keeps the number of symbols between two $\sharp$'s as $n$;
* an *add-one checker*, which guarantees that only symbols with the form $\sharp{x \atop x+1}\sharp$ appears; finally,
* a *consistent checker*, which guarantees that only symbols with the form $\sharp{x \atop y}\sharp{y \atop z}\sharp$ can appear concurrently.

Note that we do want to accept $\Sigma^\*-\{s\_n\}$ instead of $\{s\_n\}$, so once we find out that the input sequence is disobeying one of the above behaviors, we accept the sequence immediately. Otherwise after $|s\_n|$ steps, the NFA will be in the only possible rejecting state. And if the sequence is longer than $|s\_n|$, the NFA also accepts. So any NFA satisfies the above five conditions will only reject $s\_n$.

It may be easy to check the following figure directly instead of a rigorous proof:

![NFA for rejecting s_n](https://i.sstatic.net/0lBw0.jpg)

We start at the upper-left state. The first part is the starter, and the counter, then the consistent checker, the terminator, finally the add-one checker. All the arc with no terminal nodes point to the bottom-right state, which is an all time acceptor. Some of the edges are not labeled due to lack of spaces, but they can be recovered easily. A dash line represents a sequence of $n-1$ states with $n-2$ edges.

We can (painfully) verify that the NFA rejects $s\_n$ only, since it follows all the five rules above. So a $(5n+12)$-state NFA with $|\Sigma|=5$ has been constructed, which satisfies the requirement of the theorem.

If there's any unclearliness/problem with the construction, please leave a comment and I'll try to explain/fix it.

---

This question has been studied by [Jeffrey O. Shallit](http://www.cs.uwaterloo.ca/~shallit/) et al., and indeed the optimal value of $f(n)$ is still open for $|\Sigma|>1$. (As for unary language, see the comments in [Tsuyoshi's answer](https://cstheory.stackexchange.com/questions/3496/conditions-for-nfa-universality/3502#3502))

In page 46-51 of [his talk on universality](http://www.cs.uwaterloo.ca/~shallit/Talks/re.ps), he provided a construction such that:

> **Theorem.** For $n\geq N$ for some $N$ large enough, there is an $n$-state NFA $M$ over binary alphabets such that the shortest string not in $L(M)$ is of length $\Omega(2^{cn})$ for $c=1/75$.

Thus the optimal value for $f(n)$ is somewhere between $2^{n/75}$ and $2^n$. I'm not sure if the result by Shallit has been improved in recent years.

> **Comments:**
> **username_1**: I'm playing with Shallit's work, hope to get a better bound much near $2^n$. Their construction seems interesting, by specify some sequence of length $\hat{\Omega}(2^n)$ which can not be represent by a "short" regular expression of length $cn+o(n)$, and each regular expression of length $f(n)$ can be described by an NFA of size $f(n)+1$. Currently I'm able to let $c \leq 22$, but a smarter idea is need to come close $2^n$.  
> **username_2**: I don't think it gives further insights for studying this problem, but the proper scholarly reference for Shallit's talk is: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)  
> **username_1**: @Hermann: Thank you for the reference, currently I cannot access to the paper, but I will find a way to.  
> **username_1**: I think by using *counter* we can replace the *starter* and *terminator* by a 2-state tiny machine. So this further reduce the size of NFA to $3n+O(1)$.  
> **username_2**: The author's preprint version of the noted JALC paper is here: https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf The bound, and the proof is the same in the printed version.  

---

