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:
- Start state
- Transition Function
- 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?
Best Answer
Your solution looks correct, If you are looking for a formula
For $k$ states and $i$ input alphabets