10
$\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$
3
  • 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.
    Commented Feb 22, 2017 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$ Commented Feb 22, 2017 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
    Commented Feb 22, 2017 at 8:42

2 Answers 2

8
$\begingroup$

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

$\endgroup$
7
  • $\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
    Commented Feb 22, 2017 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
    Commented Feb 22, 2017 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
    Commented Feb 22, 2017 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
    Commented Feb 22, 2017 at 10:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aryeh
    Commented Feb 22, 2017 at 10:47
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 and acknowledge you have read our privacy policy.

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