in Theory of Computation recategorized by
570 views
1 vote
1 vote

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

  1. $16$
  2. $26$
  3. $32$
  4. $64$
in Theory of Computation recategorized by
570 views

1 Answer

3 votes
3 votes

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?
0
0
Answer:

Related questions