1 votes 1 votes How many DFA's exits with two states over input alphabet $\left \{ 0,1 \right \}$ $16$ $26$ $32$ $64$ Theory of Computation nielit2017dec-assistanta theory-of-computation finite-automata number-of-dfa + – admin asked Mar 31, 2020 recategorized Aug 24, 2020 by Lakshman Bhaiya admin 985 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 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 Mohit Kumar 6 answered May 20, 2020 Mohit Kumar 6 comment Share Follow See all 2 Comments See all 2 2 Comments reply habedo007 commented Oct 12, 2020 reply Follow Share Why would the formula change for n = 3 in your reference link? 0 votes 0 votes chirag_soni_07 commented Oct 14, 2023 reply Follow Share but why multiply by 4? Can we have FA with no final states? 0 votes 0 votes Please log in or register to add a comment.