9
$\begingroup$

I have a question regarding counting DFAs:

Given a Σ = {0, 1} input string, with the state set Q = {1...n}, how would I find the total number of DFAs that can be constructed?

I believe this is a combinatorics problem, but I am not really sure what I would have to multiply.

Thanks.

Improve this question
$\endgroup$
5
  • $\begingroup$ Not entirely sure what you mean by "could be constructed". Do you mean one DFA has state 1, another has states 1 and 2, another has states 1, 2 and 3, etc? In that case, you need to look at all the possible subsets of 1 through n states. There's a special name for this, but I'll let you figure it out. $\endgroup$
    – musical_coder
    Sep 19, 2013 at 4:22
  • $\begingroup$ Note: It depends on language also! so every possible deterministic transition diagram may not necessary a DFA of language.- So not just a combinatorics problem. $\endgroup$
    – Grijesh Chauhan
    Sep 19, 2013 at 4:23
  • $\begingroup$ Was going to answer, but it's tricky. Here's what I got: A DFA is defined by a set of states, a set of edges from state to state, and the initial state. So it's a directed graph. A binary DFA has exactly two edges from each state. Each state must be reachable from the initial state, which is a stronger requirement than being "connected" but weaker than being "strongly connected." $\endgroup$
    – Potatoswatter
    Sep 19, 2013 at 4:29
  • 1
    $\begingroup$ Is the state number supposed to be an observable output? I would think that two DFAs with the same topology but differently-numbered states would be the same. But it's not clear from the question. It's not observable, this is a really tough question, meriting a publication. $\endgroup$
    – Potatoswatter
    Sep 19, 2013 at 4:55
  • $\begingroup$ this problem is not phrased here mathematically/exactly, but a careful/rigorous reformulation is probably "deep". seems to be similar to graph isomorphism. also a natural/obvious generalization is to NFAs. as with JEP's answer, it is also readily amenable to a empirical/monte carlo type estimation approach. $\endgroup$
    – vzn
    Oct 3, 2013 at 23:45

3 Answers 3

Reset to default
5
$\begingroup$

This is indeed a nontrivial problem. A solution can be found in this paper: Enumeration and Random Generation of Accessible Automata.

Improve this answer
$\endgroup$
1
$\begingroup$

Essentially its the product of all transitions possible from each possible start state to each possible set of accept states. For this example, there are n^(2n) transition possibilities. Where there are n total states, each of which has n possible transitions per edge (input symbol) giving us n^(2n). We have n possible start states, and 2^n accept states (the power set of possible states.) The product of all three of these gives us: n^(2n)*n*2^(n).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If you enforce a labeling of the states of DFAs, then your answer may be correct. Without labeling (which is how a DFAs is defined), this is not correct. You need to consider start states since you are now over counting. Consider a two state DFA whose transitions go to the other state for any symbol. Consider the two accept state case (always accepts). Since there are two states, there are two possible start states. However, these two machines are exactly alike (mirror images of each other). If you label the states, then these are technically different. But without, these DFAs are the same. $\endgroup$
    – mdxn
    Oct 4, 2013 at 1:01
1
$\begingroup$

TL;DR: $n \centerdot 2^n \centerdot n^{mn}$

where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$.

We'll go through each element of a DFA 5-tuple to figure out the various combinations that would each yield a unique DFA. The 5-tuple consists of ($Q$, $\Sigma, \delta$, $s$, F)

$s$:

Any 1 element of $Q$ can be the start state. Thus there are $\mid Q\mid$ = $n$ ways to choose $s$.

F:

Any number of elements of Q can be accept states, therefore all subsets of Q are valid choices for F. The number of possible subsets for a set of cardinality n is 2$^n$. Another way to say this is the cardinality of $Q$'$s$ power set $P(Q)$ is 2$^n$

$\delta$:

$\delta$ is defined as f: $Q$ x $\Sigma\rightarrow Q$ i.e. the $\delta$ function's domain is $Q$ x $\Sigma$ and its range is $Q$. The cardinality of the domain is $mn$ where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$, and that of the range is $\mid Q\mid$ $=$ $n$. Thus there are $n^{mn}$ ways to choose $\delta$.

$Q$ and $\Sigma$ are given; there is only $1$ way to choose them.

So the total number of ways to choose amongst the 5 elements of a DFA where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$ is

$n \centerdot 2^n \centerdot n^{mn}$

Better 5 years late than never, huh?

Improve this answer
$\endgroup$
2
  • $\begingroup$ You're technically correct, but I think what OP meant was the number of distinct languages of such DFAs, not the number of DFAs (but I could be wrong). $\endgroup$
    – Ryan Dougherty
    Feb 15, 2018 at 3:55
  • $\begingroup$ Question clearly states "how would I find the total number of DFAs that can be constructed?" $\endgroup$
    – JJ Skye
    Feb 22, 2018 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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