<p>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: <a href="http://www.eatcs.org/images/bulletin/beatcs89.pdf">http://www.eatcs.org/images/bulletin/beatcs89.pdf</a></p>

CC BY-SA 3.0
2011-08-22T23:58:50.820Z
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
CC BY-SA 3.0
2011-08-23T11:31:42.383Z
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
CC BY-SA 3.0
2011-08-23T11:35:43.987Z
And, from the same author, we have the article [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), 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
CC BY-SA 3.0
2011-08-22T22:35:43.300Z
2011-08-23T18:37:35.347Z
2011-08-23T18:37:35.347Z
Hermann Gruber
<p>The question is simple and direct: For a fixed <span class="math-container">$n$</span>, how many (different) languages are accepted by a DFA of size <span class="math-container">$n$</span> (i.e. <span class="math-container">$n$</span> states)? I will formally state this:</p>
<blockquote>
<p>Define a DFA as <span class="math-container">$(Q,\Sigma,\delta,q_0,F)$</span>, where everything is as usual and <span class="math-container">$\delta:Q\times\Sigma\to Q$</span> is a (possibly partial) function. We need to establish this since sometimes only total functions are considered valid.</p>
<p>For every <span class="math-container">$n\geq 1$</span>, define the (equivalence) relation <span class="math-container">$\sim_n$</span> on the set of all DFAs as: <span class="math-container">$\mathcal{A}\sim_n\mathcal{B}$</span> if <span class="math-container">$|\mathcal{A}|=|\mathcal{B}|=n$</span> and <span class="math-container">$L(\mathcal{A})=L(\mathcal{B})$</span>.</p>
<p>The question is, then: for a given <span class="math-container">$n$</span>, what is the index of <span class="math-container">$\sim_n$</span>? That is, what is the size of the set <span class="math-container">$\{L(\mathcal{A})\mid\mathcal{A}\textrm{ is a DFA of size }n\}$</span>?</p>
</blockquote>
<p>Even when <span class="math-container">$\delta$</span> 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 <em>many</em> graphs of size <span class="math-container">$n$</span> accepting <span class="math-container">$\Sigma^*$</span>. Same with other trivial combinations for the empty language and other languages whose minimal DFA has fewer than <span class="math-container">$n$</span> states.</p>
<p>(A naïve) recursion doesn't seem to work either. If we take a DFA of size <span class="math-container">$k$</span> 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.</p>
<p>Any thoughts?</p>
<p><strong>Note.</strong> I updated the question again, with a formal statement and without the previous distracting elements.</p>

CC BY-SA 3.0
2011-08-22T12:48:34.630Z
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
CC BY-SA 3.0
2011-08-22T12:57:42.213Z
Apologies: For the regex example, it should be "a*a*a*a*a*", as that does allow any number.
Evgenij Thorstensen
CC BY-SA 3.0
2011-08-22T14:11:34.530Z
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
CC BY-SA 3.0
2011-08-22T14:13:07.887Z
@EvgenijThorstensen Well, yes, the question is about how many different languages. With respect to your example, I hadn't considered that, but you're definitely correct. I will take that part out of the question, since it's just a distraction. There should be some notion of "minimal regular expression" involved. I will think about it.
Janoma
CC BY-SA 3.0
2011-08-22T14:14:42.253Z
@mhum Yep, apparently the problem is in the stars. Will think (more) about it.
Janoma
CC BY-SA 3.0
2011-08-22T14:26:46.593Z
Each regular language has a unique minimal DFA that accepts it.  I think your question could simply be: "What fraction of DFA of size $n$ are minimal?"
Lev Reyzin
CC BY-SA 3.0
2011-08-22T14:32:27.140Z
@lev-reyzin Well, that's an interesting question, but not what I want. I want to know how many languages can be accepted by a DFA of size $n$, minimal or not.
Janoma
CC BY-SA 3.0
2011-08-22T14:38:10.033Z
Oh I see; I misread it, sorry.  So you want to know number the number of equivalence classes (via their language) of DFA of size n?
Lev Reyzin
CC BY-SA 3.0
2011-08-22T15:15:00.080Z
Assuming the relations are $\mathcal{A}\sim_n\mathcal{B}$ if $|\mathcal{A}|=|\mathcal{B}|=n$ and $L(\mathcal{A})=L(\mathcal{B})$, then yes, I want to know the number of equivalence classes of $\sim_n$ for every $n$. That's an elegant way of stating it, but I don't think it makes it easier :-)
Janoma
CC BY-SA 3.0
2011-08-22T15:41:33.557Z
Trivial observation: $n+1$ states can be used to define at least $2^n$ different languages.
Evgenij Thorstensen
CC BY-SA 3.0
2011-08-22T21:56:44.033Z
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
CC BY-SA 3.0
2017-04-19T14:32:43.117Z
See also the related question https://cstheory.stackexchange.com/q/37980/109
András Salamon
<co.combinatorics><fl.formal-languages><automata-theory><regular-language><dfa>
What is the number of languages accepted by a DFA of size $n$?
Janoma
# What is the number of languages accepted by a DFA of size $n$?

(Asked by: username_0 on 2011-08-22)

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.

**Tags:** co.combinatorics, fl.formal-languages, automata-theory, regular-language, dfa
> **Comments:**
> **username_1**: 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?  
> **username_1**: Apologies: For the regex example, it should be "a*a*a*a*a*", as that does allow any number.  
> **username_2**: 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).  
> **username_0**: @EvgenijThorstensen Well, yes, the question is about how many different languages. With respect to your example, I hadn't considered that, but you're definitely correct. I will take that part out of the question, since it's just a distraction. There should be some notion of "minimal regular expression" involved. I will think about it.  
> **username_0**: @mhum Yep, apparently the problem is in the stars. Will think (more) about it.  
> **username_3**: Each regular language has a unique minimal DFA that accepts it.  I think your question could simply be: "What fraction of DFA of size $n$ are minimal?"  
> **username_0**: @lev-reyzin Well, that's an interesting question, but not what I want. I want to know how many languages can be accepted by a DFA of size $n$, minimal or not.  
> **username_3**: Oh I see; I misread it, sorry.  So you want to know number the number of equivalence classes (via their language) of DFA of size n?  
> **username_0**: Assuming the relations are $\mathcal{A}\sim_n\mathcal{B}$ if $|\mathcal{A}|=|\mathcal{B}|=n$ and $L(\mathcal{A})=L(\mathcal{B})$, then yes, I want to know the number of equivalence classes of $\sim_n$ for every $n$. That's an elegant way of stating it, but I don't think it makes it easier :-)  
> **username_1**: Trivial observation: $n+1$ states can be used to define at least $2^n$ different languages.  
> **username_4**: 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)}$?  
> **username_5**: See also the related question https://cstheory.stackexchange.com/q/37980/109  

---

## 1 answers

### Answer by username_6 on 2011-08-22. Score: 20 | Accepted answer

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>

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: And, from the same author, we have the article [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), 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$).  

---

