Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

Question

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?

Answer 1

Without output

The state space has $n$ elements and the input space has $2$ elements. The state transition function maps the possible input-state pairs into the states. There are $2n$ such pairs. That is, we are talking about functions that map sets of $2n$ elements onto sets of $n$ elements. There are $$n^{2n}$$ such functions since any pair of input-state can be associated with any state.

With output

Assume that there is always an output. Then every state-input pair generates an output. Now, we have functions mapping sets of $2n$ elements onto sets of $a$ elements. There are $$a^{2n}$$ such functions. Together with the state transition functions we have $$n^{2n}a^{2n}$$ possibilities.

May or may not

I can interpret the "may or may not" clause in the following way. There are $a+1$ outputs, one of them is the "no output".

Appendix

Why do we have $2n$ possible pairs of inputs and states when we have $n$ states and $2$ inputs?

For $n=1$ we have $(0,1)$ and $(1,1)$, that is $2\times 1=2n$ possible pairs of inputs and states. Assume, that for all $k \le n$ we have $2k$ such elements of the range of the state transition function. Let's see how many pairs we have if the number of states is $n+1$. For the elements of the form $(i,k), k\le n, i=0,1$ we will have to add $(i,n+1), i=0,1$, that is two more pairs. $2n+2=2(n+1)$. By the principle of mathematical induction, it has been proved that for all $n$ the number of pairs is $2n$.

I hope that it it does not need any further argumentation that the number of possible state transition functions is $n^{2n}$.

Example

Let the set of states be $\{\spadesuit, \heartsuit,\diamondsuit, \clubsuit\}$ and let the set of inputs be $\{0,1\}$. The set of possible pairs of inputs and states is $$\{(0,\spadesuit),(0,\heartsuit),(0,\diamondsuit),(0,\clubsuit),(1,\spadesuit),(1,\heartsuit),(1,\diamondsuit),(1,\clubsuit)\}.$$

Every such pair may trigger $4$ new states. For example

$$(0,\spadesuit)\rightarrow\spadesuit, (0,\spadesuit)\rightarrow\heartsuit, (0,\spadesuit)\rightarrow\diamondsuit,(0,\spadesuit)\rightarrow\clubsuit.$$

As a total, we have $4^8=n^{2n}$ distinct state transition functions.

Answer 2

Imagine a transition table with $n$ rows, and columns with pairs (new-state, write) given read 0, (new-state, write) given read 1.

There are $n^2a^2$ ways to make each row. There are $n$ rows. The total number of machines is thus $n^{n^{2}a^{2}}$. Add 1 to $a$ to account for an empty "no-write" character.

When I get enough reputation points I'll post an image of the transition table.