No of DFA

Question

How many number of FA are possible with N states (Q1,Q1,........Qn) for input alphabet {1,2,3,........m} ,where Q1 is always initial state ?

Comments

yes, m + 1

then , total e- NFA will be ==> ( 2 ^ n ^ n(m + 1) ) * 2 ^ n , rt?

---

yes,

but didn't understand if there is nothing among all or some states...

---

https://gateoverflow.in/40678/ugcnet-dec2015-iii-27?show=40754#a40754

Answer 1

entries in the table represent choices for a particular state and input

Comments

thanks @sanket

Answer 2

Input set is given. So, we have 3 parts of DFA which we can change: 

1. Start state

2. Transition Function

3. Final state

Start state can be chosen as any one among N in N ways.

Transition function is from Q ⨯ Z to Q, where Q is the set of states and Z is the alphabet state. |Q| = n, |Z| = m. So, number of possible transition functions = Q^{(Q * Z)} = n^nm

Final state can be any subset of the set of states including empty set. With n states, we can have 2ⁿ possible sub states. 

we can have the formula n × (n^(nm))  × 2n=(n^(mn+1)) × 2n