if we have n states and k input symbols and assuming that the no of final state may be any subset of these n states.
no of ways to choose initial state = 1 (as the intial state is fixed)
no of final state = 2^n (as we have two possibility -->1> choose a state and keep in our subset of final state or 2>do not choose it)
no of different dfa assuming no final state and no initial state is n^(n*k) because
input alphabate a b
state1 | dfa can go to any of the 3 staes | dfa can go to any of the 3 staes |
state 2 | dfa can go to any of the 3 staes | dfa can go to any of the 3 staes |
state3 | dfa can go to any of the 3 staes | dfa can go to any of the 3 staes |
so,total no of state= (no of way to select initial state)(no of way to select final state)(no of way to select different dfa with is not designated by a final state or initial state)
= 1*2^n*n^(k*n)