SELF DOUBT

Question

If we are having n states and m alphabets..how many DFAs and NFAs are possible?

Answer 1

there are totally 'n' states, 'm' alphabets.

• Each state can be final or non-final state (2 choices). So, there are 2^n variations.
• for each state, there is 'm' out edges (alphabets) having 'n' destination nodes to choose from. So, each state will add 'n * m' variations which gives us n^n*m variations.

In total, we will have 2^n * n^n*m DFA's.

Comments

and what about the no of NFAs?

---

In the above case, there should be a factor of 'n' for the number of possible initial states.(Starting state can be chosen from n states in the dfa)

Now for nfa case:

each alphabet at each state has 2^n choices to chose from(total number of subsets of states possible).So total 2^mn at each state.Thus a total of 2^(n*n*m) combining all states together.

n choices for initial state

and 2^n choices for final states as well.

This is what I think should happen!