# Finite Automata Mixture Combinatorics

Hello Folks, I am facing hard time in understanding this, basic question which says, how many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?

What i understand is:

Number of possible inputs possible: (a,X), (a,Y), (b,X), (b,Y) i.e. 4;

so each input has option of going on 2 states, which sums up to be: 2^4;

I know to find total number of DFA, we need is Total number of transition * number of final state.

so, according to me answer need to be 2^4 * 2^2 = 2^6; but actual answer is 20 ? How it can be? Please throw some light on this !! Thankyou!!

Notice that the question also requires the automaton to accept everything. This means that if e.g., $$X$$ is not accepting, then you need to discount it.
Your count of the number of transition functions is correct, $$2^4$$. However, it's not true that the total number is $$2^4$$ times the number of final states, but rather the number of options for final states. Naively, this would be $$4$$: either both $$X,Y$$ are accepting, neither, just $$X$$ or just $$Y$$.
However, $$X$$ must be accepting, otherwise the empty word is not accepted. We now have to reason about whether $$Y$$ is accepting. If it is, then all transition functions are ok, and the automaton will accept everything. Thus, you have $$2^4$$ automata with $$Y$$ accepting.
If $$Y$$ is not accepting, then not all is lost - maybe $$Y$$ is not reachable from $$X$$. This happens when both transitions from $$X$$ are back to $$X$$. In this case, you can still point the transitions from $$Y$$ wherever you want, so you get $$4$$ additional DFAs.
So in total, you have $$16+4=20$$ options.