#Number of DFAs

Question

Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states?

Comments

yes  @ Anand, u did it...

but the last term, "Possible number of transition functions" some what difficult to understand.

---

We have $10$ states .so possible number of final states $2^{10}$

for each states we have $2$ choice , make it as a final state or don't make it i.e $2$ choices for $10$ states

$2\times 2\times ...(10 \text{times}) \times2=2^{10}$

---

we can make only $1$ state as start state among $10$state i.e $\binom{10}{1}=10$

---

Transition function is

$Q \times \sum \rightarrow Q$

where 

$Q =\text{set of states}$

$\sum =\text{ possible input}$

$\left | Q \times \sum \right |=10 \times 5=50$

$\left | Q \right |=10$

Number of possible function =$10^{50}$

---

thank u .. i got it!

Answer 1

 

In the above case n=10, m=5

and yes initial state is not fixed that's why in final answer we will multiply by 10 (because I solve the question by assuming the initial state is 1 but it might be 1,2,3,4,....10 )