State Diagrams Problem 1

Solution

The domain of the transition function contains all the pairs of a state plus an action, so it has size nk. The co-domain of the function contains all sets of states, so it has size \(2^n\). We can choose the output value independently for each input value, so we have \((2^n)^{nk}\) total choices for constructing the transition function.

Wow, that's a vast number of possible state diagrams! Who would have thought?