If there is a one-to-one function from $A$ to $B$, then we know that

   |A| <= |B|

|P(A)| = |A|
 
   False

How many states (aka board configurations) does the game of chess have?

   finite


There are more functions from N to N than there are finite-length ASCII formulas.
 
   true

Sum from k=0 to n of (n choose k)

   2^n


|Z x Z| = |C|, where C is the set of complex numbers.

   false

Building a general-purpose program that can decide if another program stops or runs forever.

   impossible


f: P(N) ---> P(N x N).    Then f(emptyset) is

   a set of pairs of natural numbers 


Two state diagrams are considered the same if they are the same as
labelled graphs.  That is, they have the same number of states, with
the same structure of edges and labels on the edges.  Let's suppose
that our state diagrams all use the same finite set of actions A, and
that each state diagram has a finite set of states named 1,...n, where
n can be as large as you like.

The number of different state diagrams is:

   countably infinite


================================================================

Problem 3a:  15 points


Recall that a phone lattice is a state diagram representing a
set of words.  Each edge in a phone lattice has a single letter on it.
In a ``deterministic'' state diagram, the transition function
never returns more than one state.  That is, it returns either
the empty set or a set containing a single state.
Said another way, if you look at
any state $s$ and any letter $a$, there is never more than one edge
labelled $a$ leaving state $s$.   

(a) Draw a phone lattice representing exactly the following set of words.
Your phone lattice must be deterministic, have only one start state,
and contain no more than 14 states.  For full credit, avoid using more
states than necessary.

moodle, moon, doodle
moo, mooo, moooo, ...   [i.e. m followed by two or more o's]

                       ---
                      o| /
                       v
                       @
                       ^
                       | o
        O ---> O  ---> @ ----------> @
       /   o       o    \      n     ^
      /m                d\          /
 --> O                    > O ---->O
     \d                 d/     l
      \                 /
       O ---> O ----->O
          o      o 



(b) Suppose that we have an alphabet of p letters and a fixed set of
n states.  In how many different ways can we build a deterministic
phone lattice using these states and letters? Briefly explain your
answer or show work.


To construct the transition function:   
   For each (state,letter) pair, we have n+1 choices of output value.
      That is, n possible states we could return, plus the empty set.

  There are pn (state,letter) pairs.

So (n+1)^pn  ways to construct the transition function.

Getting that far was worth full credit.

For an extra bonus point (which didn't put anyone over 100% on the
exam but did balance other deductions): notice that we also have to
pick a start state and some number of end states.  We have n ways to
choose a start state, and 2^n ways to choose a set of end states.

So we actully have n x 2^n x (n+1)^pn ways to build the state diagram.


================================================================
================================================================