Input set is given. So, we have 3 parts of DFA which we can change:
- Start state
- Transition Function
- Final state
Start state can be chosen as any one among 3 in 3 ways.
Transition function is from Q ⨯ Z to Q, where Q is the set of states and Z is the alphabet state. |Q| = 3, |Z| = 2. So, number of possible transition functions = 3(3 * 2) = 36
Final state can be any subset of the set of states including empty set. With 3 states, we can have 23 = 8 possible sub states.
Thus total number of DFAs possible
$= 3 \times 3^6 \times 2^3 = 17496$
For $n$ states and $m$ input alphabets we can have the formula
$$n \times n^{n m} \times 2^ n = n^{mn + 1} \times 2^n $$
In a DFA there might not be a difference if start state changes- as states are unlabeled usually. In such a case, we can divide the above by number of states giving $n^{mn} \times 2^n$ possible DFAs.