The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:

Define a DFA as $(Q,\Sigma,\delta,q_0,F)$, where everything is as usual and $\delta:Q\times\Sigma\to Q$ is a (possibly partial) function. We need to establish this since sometimes only total functions are considered valid.

For every $n\geq 1$, define the (equivalence) relation $\sim_n$ on the set of all DFAs as: $\mathcal{A}\sim_n\mathcal{B}$ if $|\mathcal{A}|=|\mathcal{B}|=n$ and $L(\mathcal{A})=L(\mathcal{B})$.

The question is, then: for a given $n$, what is the index of $\sim_n$? That is, what is the size of the set $\{L(\mathcal{A})\mid\mathcal{A}\textrm{ is a DFA of size }n\}$?

Even when $\delta$ is a total function, it doesn't seem to be an easy count (for me, at least). The graph might not be connected, and the states in the connected component containing the initial state might all be accepting, so, for example, there are many graphs of size $n$ accepting $\Sigma^*$. Same with other trivial combinations for the empty language and other languages whose minimal DFA has fewer than $n$ states.

(A naïve) recursion doesn't seem to work either. If we take a DFA of size $k$ and add a new state, then, if we want to keep determinism and make the new graph connected (to try to avoid trivial cases), we have to remove a transition to connect the new state, but in that case we may lose the original language.

Any thoughts?

Note. I updated the question again, with a formal statement and without the previous distracting elements.

  • Just to clarify: Do you mean "how many different languages can one define using $n$ states?", where a language is defined using $n$ states if there is a DFA with $n$ states that accepts it. Also, for the regular expressions, the regex "a*aaaaaa" surely has > 1 concatenations, but the DFA needs only one state (two if you need a separate sink), no? – Evgenij Thorstensen Aug 22 '11 at 12:48
  • Apologies: For the regex example, it should be "aaaaa*", as that does allow any number. – Evgenij Thorstensen Aug 22 '11 at 12:57
  • The definition of $c(r)$ appears very related to the notion of "dot-depth", except that concept is normally applied to star-free languages (probably for the reasons that @Evgenij Thorstensen outlined). – mhum Aug 22 '11 at 14:11
  • 1
    Trivial observation: $n+1$ states can be used to define at least $2^n$ different languages. – Evgenij Thorstensen Aug 22 '11 at 15:41
  • 2
    We can get a little bit more, so $2^{\Omega(n)}$ seems OK. But the number of n-state automata is around $n^{cn}2^n=2^{cn\log n+n} = 2^{\Theta(n\log n)}$ (assuming $|\Sigma|=c$). Can we get $2^{\omega(n)}$? – Kaveh Aug 22 '11 at 21:56
up vote 19 down vote accepted

I think that this question has been studied previously. Mike Domaratzki wrote a survey on research in this area: "Enumeration of Formal Languages", Bull. EATCS, vol. 89 (June 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

  • 4
    The paper does address precisely the question asked, from page 120 and on. It's the function $g_k(n)$, and the paper gives rather tight bounds (close to what Kaveh mentions above) on it, although I have not inhaled all the details. – Evgenij Thorstensen Aug 22 '11 at 23:58
  • 1
    Indeed. What we want, then is $g_k(n)$, or, by the relation given, $f_k(n)$, which is the number of pairwise non-isomorphic minimal DFAs with $n$ states over a $k$-letter alphabet. I haven't looked at it in detail either, but it appears that only bounds are known, not exact quantities. – Janoma Aug 23 '11 at 11:31
  • 6
    And, from the same author, we have the article On the Number of Distinct Languages Accepted by Finite Automata with n States, which even gives explicit computations for $g_1(n)$ ($1\leq n\leq 10$), $g_2(n)$ ($1\leq n\leq 6$) and $g_3(n)$ ($1\leq n\leq 4$). – Janoma Aug 23 '11 at 11:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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