9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – D.W. Feb 22 '17 at 0:04
  • 4
    $\begingroup$ Here is a reference that may be relevent: "ON THE NUMBER OF DISTINCT LANGUAGES ACCEPTED BY FINITE AUTOMATA WITH n STATES" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838 $\endgroup$ – Michael Wehar Feb 22 '17 at 7:50
  • 2
    $\begingroup$ Thanks to both of you for correcting my mistake and giving me this reference which is indeed a relevent one. $\endgroup$ – Luz Feb 22 '17 at 8:42
7
$\begingroup$

According to Ishigami Y., Tani S. (1993) The VC-dimensions 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$.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Luz Feb 22 '17 at 10:08
  • $\begingroup$ 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. $\endgroup$ – Aryeh Feb 22 '17 at 10:12
  • $\begingroup$ oh :( then your bound is contradicting mine... since mine has a large denominator $(m-1)!$ which makes it far below yours... how come ?? $\endgroup$ – Luz Feb 22 '17 at 10:17
  • $\begingroup$ I don't quite see the contradiction -- the large denominator $(m-1)!$ is still swamped by $m^m$ in the numerator. $\endgroup$ – Aryeh Feb 22 '17 at 10:30
  • $\begingroup$ 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. $\endgroup$ – Aryeh Feb 22 '17 at 10:32
4
$\begingroup$

(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” (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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.