Finding non-trivial NFA that accepts all short strings

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.

StackExchange Computer Science Q#83749, answer score: 2