Conditions for NFA universality 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^*$?
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&gt;0 and sufficiently large n, we have f(n) &gt; 2C⋅√n.

The prime number theorem implies that for every c &lt; lg e and for sufficiently large k, there are at least c ⋅2k / k primes in the range [2k, 2k+1].  We take c=1.  For such k, let Nk = ⌈2k / k⌉ and define an NFA Mk as follows.  Let p1, …, pNk be distinct primes in the range [2k, 2k+1].  The NFA Mk has Sk=1+p1+…+pNk states.  Apart from the initial state, the states are partitioned into Nk cycles where the ith cycle has length pi.  In each cycle, all but one state are accepted states.  The initial state has Nk 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 Pk be the product p1…pNk.  It is easy to see that Mk accepts all strings of length less than Pk but rejects the string of length Pk.  Therefore, f(Sk)≥Pk.

Note that Sk ≤ 1 + Nk⋅2k+1 = o(22k) and that Pk ≥ (2k)Nk ≥ 22k.  The rest is standard.