no of dfa

Question

https://gateoverflow.in/10853/how-many-dfas-exist-with-three-states-over-the-input-alphabet
For n states and m input alphabets we can have the formula for total no of DFA 
n×n^nm×2ⁿ=n^nm+1×2n
----  my doubt is that can we generalize a result like above for no of dfa that accepts empty language.
after so many effort i m not able to get that... 

Answer 1

Yes of course we can generalise it.

We know that for a dfa comprising of n states and m input alphabets ,

No of DFA possible = n * n^nm * 2ⁿ assuming that the DFA is a labelled one and hence the choice of start state matters

Now coming to your question , we need to accept an empty language.As we know final states are meant for acceptance only.So if we want that we accept the empty language what we need to do is just we do not choose any of the states as the final state and hence all states will be rejecting states and hence we will get empty language.By empty language we mean nothing is accepted.

So given an initial state there is only 1 way of choosing final state and that is not choosing any of the state as the final state

Hence the 3rd term "2ⁿ" in general expression reduces to 1 only.

Hence no of DFA which accepts empty language = n * n^nm

                                                                       =  n^nm+1

Comments

@habibkhan i think in a dfa(out of n * n^nm * 2ⁿ  ) that have no final state accept empty language no doubt but what about those dfa^s which contains final state and that final state is unreachable .
for example suppose n=2 and m=2(0,1) so no of dfa that are not having any final state=n * n^nm  = 32
but no of dfa that accept empty language are 40 so we have 8 extra i think these r comming bcoz of  " final state that is unreachable"
am i right ??
nd thnx for ur effort......

---

is this not a valid DFA that accept empty language 
    

---

Ya I got ur point but such dfa's are already counted.U cannot double count for them

---

but this dfa has a final state nd according to ur result n*n^mn this have no final state and
plzz varify this with for example suppose n=2 and m=2(0,1) so no of dfa that are not having any final state=n * n^nm  = 32 
but no of dfa that accept empty language are 40 so we have 8 extra

---

Ok I got ur point..Yes I agree that it is going to be complicated.Convinced