number of NFAs given $a$ states

Question

If $a$ and $b$ are positive integers. How many NFAs can there be with $a$ states and the input alphabet, $\Sigma = \{0, 1, . . . , b − 1\}$

Answer 1

HINT: You’ll need factors to account for each of the following:

• the set of initial states;
• the set of acceptor states; and
• for each state, the set of transitions out of that state.

The first two are straightforward. For the third, notice that each of the $b+1$ possible transitions from a given state has $b+1$ possible targets: it can go to any state, or it can be omitted altogether. Why $b+1$ and not $b$? To account for $\epsilon$-transitions (or $\lambda$-transitions, if you use that notation for the empty word).

Answer 2

Number of possible initial states : $a$
Number of possible final states : $2^a$
Number of possible transitions: (as shown above) : $(b+1)^(a^2)$ and for each of these transitions we have $2^a$ possible states. So total choices : $2^(b+1)^(a^2)$

So possible number of NFAs : $a*2^a* 2^(b+1)^(a^2)$