611 views

How many DFA's exits  with two states over input alphabet $\left \{ 0,1 \right \}$

1. $16$
2. $26$
3. $32$
4. $64$

For n states and m input alphabets we can have the formula:

$n*n^{nm}*2^{n}$

=$n^{mn+1}*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}×2^{n}$ possible $DFAs$.

Given $n=2,m=2$

$n^{mn}×2^{n}$

$2^{2*2}×2^{2}$

$16*4$

=$64$

Option D

https://gateoverflow.in/10853/how-many-dfas-exist-with-three-states-over-the-input-alphabet

### 1 comment

Why would the formula change for n = 3 in your reference link?

1
1,199 views