<p>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$</p>

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

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

CC BY-SA 3.0
2017-04-16T06:08:40.373Z
Preprint: http://www.cs.umanitoba.ca/~mdomarat/pubs/enum_jalc.pdf
András Salamon
CC BY-SA 3.0
2017-04-13T13:15:57.830Z
2017-04-13T13:15:57.830Z
Jeffrey Shallit
<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>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.</p>

<blockquote>
  <p>Is it known whether $\lg N_n'$ is close to $(\lg D_n')^2$?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2017-04-19T14:32:22.503Z
See also the related question https://cstheory.stackexchange.com/q/7913/109
András Salamon
<cc.complexity-theory><automata-theory><space-bounded><space-complexity>
Quadratic relationship between nondeterministic and deterministic space?
András Salamon
# Quadratic relationship between nondeterministic and deterministic space?

(Asked by: username_0 on 2017-04-13)

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.

**Tags:** cc.complexity-theory, automata-theory, space-bounded, space-complexity

> **Comments:**
> **username_0**: See also the related question https://cstheory.stackexchange.com/q/7913/109  

---

## 1 answers

### Answer by username_1 on 2017-04-13. Score: 19 | Accepted answer

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

> **Comments:**
> **username_0**: Preprint: http://www.cs.umanitoba.ca/~mdomarat/pubs/enum_jalc.pdf  

---

