State Diagrams Problem 1


A state diagram transition function sounds like quite a complicated object. It's tempting to have a panic and improvise. Don't go there. Attack the problem systematically.

First, figure out (or look up) how to calculate the number of ways to build a function from a set of size p to a set of size q. There's a general formula for this.

Ok, so what is the domain of your transition function? What is the co-domain? Remember that our transition functions return sets of states, not single states. This is also something you can look up if you don't remember.

Now, how big is the co-domain? How big is the domain?

Finally, put all the pieces together.