Quadratic relationship between nondeterministic and deterministic space?

Question

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.

Suppose we approach the problem from the other end. For simplicity, assume the Boolean alphabet. The amount of space used by a TM to decide a computable language is often closely related to the logarithm of the number of states used by the automaton simulating the TM for each regular slice of a language. This motivates the following question.

Let $D_n$ be the number of syntactically distinct DFAs with $n$ states, and let $N_n$ be the number of distinct NFAs with $n$ states. It is straightforward to show that $\lg N_n$ is close to $(\lg D_n)^2$.

Further, let $D_n'$ be the number of distinct regular languages that can be recognised by a DFA with $n$ states, and let $N_n'$ be the number recognised by an NFA.

Is it known whether $\lg N_n'$ is close to $(\lg D_n')^2$?

It is not clear to me how $D_n$ and $D_n'$, or $N_n$ and $N_n'$, are related to each other, or how closely. If all this relates to a well known question in automata theory then a hint or pointer would be appreciated. The same question is also relevant for two-way automata, due to the same reasoning, and I am especially interested in this version.

Answer 1

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct languages accepted by DFA's, then for fixed $k \geq 2$

(i) $\log g_k (n)$ is, up to smaller order terms, asymptotically $kn\log n$

(ii) $\log G_k (n)$ is, up to smaller order terms, asymptotically between $(k-1)n^2$ and $kn^2$.