Main goal:  basic notation and concepts for state machines


(1) Lead example:  phone lattice

   Key points to touch on
      * marking for start/end states
      * only one start, multiple end states
      * actions are on edges 
      * can have multi-edges
      * loops, esp. for phone lattices
      * can have two next states for same state+action


   hat, cat, mat, ham 

   built reasonable phone lattice
   at start of lattice, why can't we send c,h,m all to same next state?
   modified to include hats and hams.   then just hats.

   modified to a less efficient non-deterministic lattice with one
      branch for each word.   Could get this as first step processing
      dictionary into lattice.   Example of a word with more than one
      dictionary pronunciation:  "get" [g eh t] [g ih t] [g iy y uh t]

   built lattice for hmm* with loop
   two possible places to put loop
   

(2) Jug puzzle

   You have two jugs, 5 gallon and 3 gallon.   How to measure out exactly
       4 gallons?   A sizeable minority of class had seen this in the movie
       "Die Hard 3"

   Represent states as x/y.   How many states?  (24)

   Draw out part of the state diagram.   
       Show some loops, both small (e.g. reversable actions) and larger
       Show solution:  path from start state to end state (mark both)
       Are all states reacheable?  [Volunteers said "yes."  We didn't check,]

(3) Representing numbers (from last spring)

In a chemistry lab report, a measurement consists of
some number of digits, optionally followed by
a decimal point and more digits, plus (not optional)
the symbol for a unit.  Suppose the units are
cm, s, ml, $\ ^\circ$.

   Good excuse to use regex notation informally.  Use your favorite 
      version of the syntax.

   First firm up what number formats are really allowed.  Esp.
        * Units are required!  [Chemists are picky]
        * leading zeros ok? [No]
        * if not, do need to allow just 0 
        * can a number start with the decimal point or does it have
          a leading zero? [Folks differ on this]
        * are trailing zeros ok? [Chemistry answer is yes]
        * can a number end with just the decimal point [no, yuck]
        * helps to define short-hand for sets
           [U] = set of units
           [D] = digits
           [N] = non-zero digits

   Then draw state diagram.   

(4) Trailer for next lecture

   What is the transition function?

   An input looks like (s,a).   Explore outputs for some sample inputs for
       various of the example graphs above.   
        * need to allow no output
        * need to allow multiple outputs
        So each output is a set of states.

   So type signature is delta: SxA --> P(S)
       

-------------------

(*) Representation of transition functions

  phone lattice for recipe transcription
     cook, cup, cut
     dice slice
  make it non-deterministic e.g. fresh out of dictionary
  
  Remind them of type signature for the transition function delta
  Show how to write a simple ASCII file representation for the lattice
  Options for storing this internally to computer program
     * 2D array.  oops, real sparse, try 1D array
     * but our states and/or actions might not be small numbers?
       need to map them to small numbers to be array indices.
       --> hash functions
     * can make a hash function that turns a (s,a) pair into a small
       integer:   details nasty, but most reasonable languages have
       built-in or easily acquired "hash table" packages