# How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

My attempt :

Input set is given. So, we have 3 parts of DFA which we can change:

1. Start state
2. Transition Function
3. Final state

Start state can be chosen as any one among 2 in 2 ways.

Transition function is from $Q \times Z$ to $Q$, where $Q$ is the set of states and $Z$ is the alphabet. $|Q| = 2$, $|Z| = 2$. So, number of possible transition functions $= 2^{2 \times 2} = 2^{4}$

Final state can be any subset of the set of states including the empty set. With $2$ states, we can have $2^2 = 4$ possible sub states.

Thus total number of DFAs possible :

$=2\times2^4\times4=128$.

Where total 40 DFA's are accepting empty language.

Can you explain in formal way, with a formula, please?

• Your title and your question do not match: Two states or three states? – Lee Mosher Feb 3 '16 at 13:24
• Sorry for typo. Thanks. – 1 0 Feb 3 '16 at 13:25
• Your attempt seems to be very clean. What kind of formula do you wish? – J.-E. Pin Feb 3 '16 at 14:04
• Assume, if we have $n$ states, over total input alphabet is $m$ . Then what will be total number of DFAs and how many DFAs accepted empty languages ? – 1 0 Feb 3 '16 at 14:13
• Why don't you apply the same argument to the general case? – J.-E. Pin Feb 3 '16 at 15:09

For $k$ states and $i$ input alphabets
$$k^{ki+1}\times 2^{k}$$