It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$.

But is this upper bound asymptotically tight ?

I found a rough sub-exponential bound in this strategy.

Let $p_i$ be an $i$-th prime.

On the singleton alphabet, $\Sigma = \{a\}$, the following NFA rejects only

$\{a^n:n>0, p_1\cdots p_k|n\}$. With $p_1+p_2+\cdots+p_k+O(1) = \Theta(k^2\log k)$ states.

Initial state $q$, is an acceptance state and it is branched into $k$ cycles with $\epsilon$ marks.

Every $i$-th cycle has $p_i$ states, and only rejecting state is the state directly linked into initial state $q$. All of its transition are marked by $a$.

It is clear that the complement of accepting language is $\{a^n:n>0, p_1\cdots p_k|n\}$ as given.

But $p_1\cdots p_k=O(e^{\Theta(k\log k)})$. which is sub-exponential with respect to $\Theta(k^2\log k)$.

In this unary and multiplication strategy it seems to be this is optimal because $\text{lcm}\{p_1,p_2,\cdots,p_n\}$ is probably maximized with constraint $p_1+\cdots+p_n=C$ under this prime summation partition.

It seems we should use multi-ary language to improve this bound. Is there any suggestion or results in research?


Your question is very similar to a similar question about regular expressions. My answer there (citing a paper of Jeff Shallit and his students) gives an example in which the minimal word not accepted has length exponential in the number of states (using the fact that a regular expression of length $\ell$ can be converted an NFA of length $O(\ell)$). Moreover, the NFAs are over a fixed alphabet.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.