<p>According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with <span class="math-container">$n$</span> states,
<a href="http://link.springer.com/chapter/10.1007/3-540-57370-4_58" rel="nofollow noreferrer">http://link.springer.com/chapter/10.1007/3-540-57370-4_58</a>
,
the VC-dimension of the concept class of <span class="math-container">$n$</span>-state DFAs over an alphabet of size <span class="math-container">$k$</span> is
<span class="math-container">$$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$</span>
It follows that there are at least <span class="math-container">$2^d$</span> distinct <span class="math-container">$n$</span>-state automata on a <span class="math-container">$k$</span>-letter alphabet. The upper bound on the number such automata follows from a simple counting argument (given in the paper), and is at most <span class="math-container">$2^d$</span>.</p>

CC BY-SA 3.0
2017-02-22T10:08:59.503Z
Thanks. I understand from your answer that there are $m^{(|\Sigma| - 1 + o(1)) m}$ $m$-states DFAs (at least and at most). But I am interested in counting minimal DFAs. Thus your upper bound does not contradict the one given in my answer, right ?
Luz
CC BY-SA 3.0
2017-02-22T10:12:29.243Z
I think this counts minimal DFAs as well, since VC-dimension is representation-independent, it's actually counting distinct *languages* -- which correspond to minimal DFAs.
Aryeh
CC BY-SA 3.0
2017-02-22T10:17:38.170Z
oh :( then your bound is contradicting mine... since mine has a large denominator $(m-1)!$ which makes it far below yours... how come ??
Luz
CC BY-SA 3.0
2017-02-22T10:30:47.110Z
I don't quite see the contradiction -- the large denominator $(m-1)!$ is still swamped by $m^m$ in the numerator.
Aryeh
CC BY-SA 3.0
2017-02-22T10:32:18.753Z
In fact, if you look at the proof of Thm. 3.2 in the paper I linked, you'll see that exact expression in the denominator.
Aryeh
CC BY-SA 3.0
2017-02-22T10:40:17.247Z
So this makes the bound you give better than the one I gave right ?
Luz
CC BY-SA 3.0
2017-02-22T10:47:41.673Z
The upper bound I think is the same as yours. The main thrust of the VC argument is that there's a nearly matching lower bound.
Aryeh
CC BY-SA 4.0
2017-02-22T09:56:31.723Z
2021-02-10T10:44:31.783Z
2021-02-10T10:44:31.783Z
Aryeh
<p><i>(NB: the upper bound given in the accepted answer is better or equal to the one given here)</i></p>

<p>An upper bound is proposed in this paper given in one of the previous comments: <em>“<a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=80F4BE077A0F53CD25C17261EA2398CD?doi=10.1.1.8.2838&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">On the number of distinct languages accepted by finite automata with n states</a>” (2002, M. Domaratzki, D. Kisman, J. Shallit)</em>.</p>

<p>In this paper: </p>

<ul>
<li>the $f_{|\Sigma|}(m)$ function provides <em>the number of distinct non-isomorphic minimal DFAs with $m$-states over a ${|\Sigma|}$-letter alphabet</em>,</li>
<li>the $g_{|\Sigma|}(m)$ function gives <em>the number of distinct languages accepted by DFAs with $m$ states over a ${|\Sigma|}$-letter alphabet</em>.</li>
</ul>

<p>We are interested in the upper bound for the $g_{|\Sigma|}(m)$ function, since my question ask for an upper bound on the number of minimal DFAs with <em>at most</em> $m$ states (and not exactly $m$).</p>

<p>What I understand from the page $6$ below Theorem $8$ is that $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ which is a better bound than the one given in my question (i.e. $2^m\cdot m^{|\Sigma|m+1}$). This partially answers my question.</p>

<p>But the paper claims that this upper bound is trivial and can be improved. However, the improvement only deals with $f_{|\Sigma|}(m)$ (as far as I understand it).</p>

CC BY-SA 3.0
2017-02-22T09:24:23.633Z
2017-02-22T13:46:11.763Z
2017-02-22T13:46:11.763Z
Luz
<p>Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$.  Let $f(m)$ denote the number of different such minimal DFAs.</p>

<p>Can we find a closed-form formula for $f(m)$?</p>

<p>Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs (as suggested in the comments). In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$.</p>

<p>We can generalize to an arbitrary alphabet $\Sigma$: the bound becomes $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$.  </p>

<p>But we bounded here arbitrary DFAs and I'm interested in bounding the number of minimal DFAs. Thus, it looks like this bound could be tighter... Does someone have a better estimate?  </p>

<p>I would appreciate if possible, some papers related to this problem or a proof/counter-example.</p>

CC BY-SA 3.0
2017-02-22T00:04:09.043Z
I don't think your upper bound is correct.  It looks like it should be $f(m) \le m \times 2^m \times m^{2m}$, rather than $f(m) \le m \times 2^m \times 2^{2m}$.  For each node, consider the two arcs leading out from that node; there are $m$ possibilities for where the first arc goes, and $m$ possibilities for where the second arc goes, so $m^2$ possibilities in total.  There are $m$ nodes, so we obtain $(m^2)^m = m^{2m}$ possibilities for the set of arcs.  The generalization would be $f(m) \le m \times 2^m \times m^{|\Sigma| m}$.
D.W.
CC BY-SA 3.0
2017-02-22T07:50:15.180Z
Here is a reference that may be relevent: "ON THE NUMBER OF DISTINCT LANGUAGES ACCEPTED BY FINITE AUTOMATA WITH n STATES" - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838
Michael Wehar
CC BY-SA 3.0
2017-02-22T08:42:51.940Z
Thanks to both of you for correcting my mistake and giving me this reference which is indeed a relevent one.
Luz
<cc.complexity-theory><automata-theory><nondeterminism><dfa>
Number of minimal DFAs of size at most $m$?
Luz
# Number of minimal DFAs of size at most $m$?

(Asked by: username_0 on 2017-02-21)

Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs.

Can we find a closed-form formula for $f(m)$?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs (as suggested in the comments). In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$.

We can generalize to an arbitrary alphabet $\Sigma$: the bound becomes $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$.

But we bounded here arbitrary DFAs and I'm interested in bounding the number of minimal DFAs. Thus, it looks like this bound could be tighter... Does someone have a better estimate?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

**Tags:** cc.complexity-theory, automata-theory, nondeterminism, dfa
> **Comments:**
> **username_1**: I don't think your upper bound is correct.  It looks like it should be $f(m) \le m \times 2^m \times m^{2m}$, rather than $f(m) \le m \times 2^m \times 2^{2m}$.  For each node, consider the two arcs leading out from that node; there are $m$ possibilities for where the first arc goes, and $m$ possibilities for where the second arc goes, so $m^2$ possibilities in total.  There are $m$ nodes, so we obtain $(m^2)^m = m^{2m}$ possibilities for the set of arcs.  The generalization would be $f(m) \le m \times 2^m \times m^{|\Sigma| m}$.  
> **username_2**: Here is a reference that may be relevent: "ON THE NUMBER OF DISTINCT LANGUAGES ACCEPTED BY FINITE AUTOMATA WITH n STATES" - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838  
> **username_0**: Thanks to both of you for correcting my mistake and giving me this reference which is indeed a relevent one.  

---

## 2 answers

### Answer by username_3 on 2017-02-22. Score: 8 | Accepted answer

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states,
<http://link.springer.com/chapter/10.1007/3-540-57370-4_58>
,
the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is
$$ d=d(n,k) := (k-1+o(1))n\log\_2 n.$$
It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-letter alphabet. The upper bound on the number such automata follows from a simple counting argument (given in the paper), and is at most $2^d$.

> **Comments:**
> **username_0**: Thanks. I understand from your answer that there are $m^{(|\Sigma| - 1 + o(1)) m}$ $m$-states DFAs (at least and at most). But I am interested in counting minimal DFAs. Thus your upper bound does not contradict the one given in my answer, right ?  
> **username_3**: I think this counts minimal DFAs as well, since VC-dimension is representation-independent, it's actually counting distinct *languages* -- which correspond to minimal DFAs.  
> **username_0**: oh :( then your bound is contradicting mine... since mine has a large denominator $(m-1)!$ which makes it far below yours... how come ??  
> **username_3**: I don't quite see the contradiction -- the large denominator $(m-1)!$ is still swamped by $m^m$ in the numerator.  
> **username_3**: In fact, if you look at the proof of Thm. 3.2 in the paper I linked, you'll see that exact expression in the denominator.  
> **username_0**: So this makes the bound you give better than the one I gave right ?  
> **username_3**: The upper bound I think is the same as yours. The main thrust of the VC argument is that there's a nearly matching lower bound.  

---

### Answer by username_0 on 2017-02-22. Score: 4

*(NB: the upper bound given in the accepted answer is better or equal to the one given here)*

An upper bound is proposed in this paper given in one of the previous comments: *“[On the number of distinct languages accepted by finite automata with n states](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=80F4BE077A0F53CD25C17261EA2398CD?doi=10.1.1.8.2838&rep=rep1&type=pdf)” (2002, M. Domaratzki, D. Kisman, J. Shallit)*.

In this paper:

* the $f\_{|\Sigma|}(m)$ function provides *the number of distinct non-isomorphic minimal DFAs with $m$-states over a ${|\Sigma|}$-letter alphabet*,
* the $g\_{|\Sigma|}(m)$ function gives *the number of distinct languages accepted by DFAs with $m$ states over a ${|\Sigma|}$-letter alphabet*.

We are interested in the upper bound for the $g\_{|\Sigma|}(m)$ function, since my question ask for an upper bound on the number of minimal DFAs with *at most* $m$ states (and not exactly $m$).

What I understand from the page $6$ below Theorem $8$ is that $g\_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ which is a better bound than the one given in my question (i.e. $2^m\cdot m^{|\Sigma|m+1}$). This partially answers my question.

But the paper claims that this upper bound is trivial and can be improved. However, the improvement only deals with $f\_{|\Sigma|}(m)$ (as far as I understand it).


---

