This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part.
The paper starts with a quite rigorous asymptotic for the number of distinct languages accepted by a DFA with $n$ states over a unary alphabet. This is done by observing under which conditions a given $n$-state unary DFA is minimal. In such cases the description of the automaton may be mapped (bijectively) to a primitive word, and the enumeration of such words is well-known and done with the help of the Möbius function. Using that result, bounds for non-unary alphabets, both in the DFA and in the NFA case, are proven.
Let's go into more detail. For a $k$-letter alphabet, define
\begin{align*}
f_k(n) &= \text{the number of pairwise non-isomorphic minimal DFA's with } n \text{ states}\\
g_k(n) &= \text{the number of distinct languages accepted by DFA's with } n \text{ states}\\
G_k(n) &= \text{the number of distinct languages accepted by NFA's with } n \text{ states}
\end{align*}
Note that $ g_k(n) = \sum_{i=1}^n f_k(i)$. We start with $f_1(k) $ and $g_1(k)$.
Enumeration of Unary DFA's
A unary DFA $M = (Q, \{a\},\delta, q_0,F) $ with states $q_0,\dots, q_{n-1}$ is minimal iff
- It is connected. Thus, after renaming, it the transition diagram consists of a loop and a tail, i.e. $\delta(q_i,a) = q_{i+1}$ and $\delta(q_{n-1},a)=q_j$ for some $j \leq n-1$.
- The loop is minimal.
- If $j \neq 0$, then either $q_{j-1} \in F $ and $q_{n-1} \notin F$ or $q_{j-1} \notin F $ and $q_{n-1} \in F$.
The loop $q_j,\dots, q_{n-1}$ is minimal iff the word $a_j \cdots a_{n-1}$ defined by
\begin{equation*}
a_i = \begin{cases}
1 \quad \text{if } q \in F, \\
0 \quad \text{if } q \notin F
\end{cases}
\end{equation*}
is primitive, which means it cannot be written in the form $x^k$
for some word $x$ and some integer $k \ge 2$.
The number $\psi_k(n)$ of primitive words of length $n$ over $k$-letter alphabets is known, see e.g. Lothaire,Combinatorics on Words. We have
\begin{equation*}
\psi_k(n) = \sum_{d | n} \mu(d) k^{n/d}
\end{equation*}
where $\mu(n)$ is the Möbius function. With the help of $ \psi_k(n) $ the paper proves exact formulas for $f_1(n)$ and $g_1(n)$ and shows that asymptotically (Theorem 5 and Corollary 6),
\begin{align*}
g_1(n) &= 2^n \left(n-\alpha+O \left(n 2^{-n/2} \right)\right) \\
f_1(n) &= 2^{n-1}\left(n+1-\alpha+O \left(n 2^{-n/2} \right)\right).
\end{align*}
Enumeration of DFA's
The next step is a lower bound for $f_k(n)$. Theorem 7 states that
\begin{equation*}
f_k(n) \ge f_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}.
\end{equation*}
For a set $\Delta \subset \Sigma$ of an automaton $M$, define $M_{\Delta}$ as the restriction of $M$ to $\Delta$.
The proof works by considering the set $S_{k,n}$ of DFA's $M$ over the $k$-letter alphabet $\{0,1,\dots,k-1 \}$ defined by
- Letting $M_{ \{0 \}}$ be one of the $f_1(n) $ different unary DFA's on $n$ states, and
- Choosing any $k-1$ functions $h_i : Q \to Q$ for $1 \le i < k$ and defining $\delta(q,i) = h_i(q)$ for $1 \le i < k$ and $q \in Q$.
The observation is then that $S_{n,k}$ contains $f_1(n) n^{ (k-1)n}$ different and minimal languages.
Enumeration of NFA's
For $G_1(n)$ one has the trivial lower bound $2^n$, since every subset $\epsilon, a,\dots, a^{n-1}$ can be accepted by some NFA with $n$ states. The lower bound is improved slightly, yet the proof is rather lengthy.
The paper Descriptional Complexity in the unary case by Pomerance et al shows that $G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n $.
Proposition 10 shows that, for $k \ge 2$ we have
\begin{equation*}
n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1.
\end{equation*}
The proof is quite short, hence I include it verbatim (more or less). For the upper bound, note that any NFA can be specified by specifying, for each pair $(q,a)$ of state and symbol, which subset of $Q$ equals $\delta(q,a)$ (hence the factor $ 2^{kn^2}$. We may assign the final states as follows: either the initial state is final or not, and since the names of the states are unimportant, we may assume the remaining final states are $\{1,\dots,k\}$ for $k \in [0..n-1]$. Finally, if we choose no final states, we obtain the empty language.
For the lower bound the authors proceed in a similar way as in the proof for the DFA case: Define an NFA $M=(Q,\Sigma,\delta,q_0, F)$ with $\Sigma = \{ 0,1,\dots,k-1 \}$, $Q=\{ q_0,\dots, q_{n-1} \}$ and $\delta$:
\begin{align*}
\delta(q_i,0) &=q_{(i+1) \mod n} \quad \text{for } 0 \le i <n \\
\delta(q_i,j) &=h_j(i) \quad \text{for } 0 \le i <n,\, 1 \le j < k
\end{align*}
where $h_j: \{ 1,\dots,n-1\} \to 2^Q$ is any set-valued function. Finally, let $F=\{q_i\}$ for any $i \in [0..n-1]$. There are $ 2^{(k-1)n^2} $ such functions and $n$ ways to choose the set of final states. One can then show that no two such NFA's accept the same language.
