Conditions for NFA universality

Question

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^*$?

Answer 1

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 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₁, …, p_Nk be distinct primes in the range [2^k, 2^k+1]. The NFA M_k has S_k=1+p₁+…+p_Nk states. Apart from the initial state, the states are partitioned into N_k cycles where the ith 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₁…p_Nk. 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(2^2k) and that P_k ≥ (2^k)^N_k ≥ 2^2k. The rest is standard.

Answer 2

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, 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:

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

In page 46-51 of his talk on universality, 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.