20
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Evgenij Thorstensen
    Commented Aug 22, 2011 at 12:48
  • $\begingroup$ Apologies: For the regex example, it should be "aaaaa*", as that does allow any number. $\endgroup$
    – Evgenij Thorstensen
    Commented Aug 22, 2011 at 12:57
  • $\begingroup$ 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). $\endgroup$
    – mhum
    Commented Aug 22, 2011 at 14:11
  • 1
    $\begingroup$ Trivial observation: $n+1$ states can be used to define at least $2^n$ different languages. $\endgroup$
    – Evgenij Thorstensen
    Commented Aug 22, 2011 at 15:41
  • 2
    $\begingroup$ 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)}$? $\endgroup$
    – Kaveh
    Commented Aug 22, 2011 at 21:56

1 Answer 1

Reset to default
20
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – Evgenij Thorstensen
    Commented Aug 22, 2011 at 23:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Aug 23, 2011 at 11:31
  • 6
    $\begingroup$ 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$). $\endgroup$
    – Janoma
    Commented Aug 23, 2011 at 11:35

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.