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

• 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 張顯之 Dec 9 '10 at 4:51

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) > 2C⋅√n.

The prime number theorem implies that for every c < 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 p1pNk. 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.

• 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 張顯之 Dec 4 '10 at 18:42
• @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 Dec 4 '10 at 19:22
• (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 Dec 4 '10 at 19:23
• (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 Dec 4 '10 at 19:25
• @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]: cs.ust.hk/mjg_lib/Library/Chro86.pdf – Hsien-Chih Chang 張顯之 Dec 5 '10 at 11:40

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

• 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 張顯之 Dec 6 '10 at 4:32
• 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 Dec 9 '10 at 19:49
• @Hermann: Thank you for the reference, currently I cannot access to the paper, but I will find a way to. – Hsien-Chih Chang 張顯之 Dec 10 '10 at 0:55
• 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 張顯之 Dec 10 '10 at 1:26
• The author's preprint version of the noted JALC paper is here: cs.uwaterloo.ca/~shallit/Papers/re3.pdf The bound, and the proof is the same in the printed version. – Hermann Gruber Mar 9 '14 at 21:59