finite state machines


A technique, particularly suited to controllers.
(Originally hardware, but also good in software.)


A small Example 
  A door-pad controller (keypresses "a","b","c"),
  which opens on the password "bcaa",
  and lights up the "denied" lamp if not.
  
  We use an internal clock "tick" input, to get us out of states
    open-door and denied, back to initial state.

  Modify: wait until four keys are pressed before indicating success/fail.
  Modify: what if we want to time-out --eg, if another button isn't pressed
    within three ticks, then go back to initial state.
  Modify, on your own: allow 3 attempts before permanently failing
    (a top-secret self-destruct suitcase)
   
 Representing FSM as a picture
 Representing FSM as a table
    (each row is a state, each column an input; entries are transitions)
    Note that you could something like this table implementaiton, in a program.
    Alternately, in OO, you'd have a State variable,
    and call its method currState = currState.advance(Input i);.
    Note that transitions might themselves be objects (!).
    (And in general in graphs, edges might be objects rather
     than just a vertex containing its list of neighbors.)

 Representing FSM as a tuple: transition functions, ...
    (Cf. a graph with labeled (multi-)edges)

  A Finite-state machine ("FSM") is:
  A tuple <S,I,t,s0>, with
    - S -- set of states    (finite :-)
    - I -- input alphabet   (finite)
    - t: S x I → S  -- transition function ("next state")
    - s0 in S -- initial state

  (This is a bit different than Rosen 11.2 or 11.3.
   We're taking the output to implicitly be based on current-state.
   He makes it explicit, and based on transition.)


Example: FSM for 3-disc CD controller:
 inputs: generated by user:    start/stop (s/s);
         generated internally: endf-disc (EOD), start-of-disc (SOD)
           (SOD means the tray has spun to the next disc and has been found)
 Some states are hooked up to the cd-spin motor,
    and some are hooked up to the try-rotate motor.

Attempt 1:
   
   state  |   S/S    EOD   SOD   
----------+--------------------
 idle     |  play    ??     ??
 play     |  idle   rotate  ??
 rotate   |  rotate  ??    play

The state "play"   is wired to the disc-spin motor, and
the state "rotate" is wired to the carousel-rotate motor.

Note that the "??" are inputs that shouldn't be generated if all goes well.
  (General policy: "fail-safe": on failure, do something safe.)

Some observations on this FSM:
  - During a rotate, we don't want to leave that state, so we
    ignore S/S.  We could fix this by adding two states:
    "rotate with intent to play", and "rotate with intent to stop".
  - We're ignoring the possibility of disc-not-found; we'll assume
    all three trays are loaded.  To really handle this, we'd need another
    internal input "disc-not-found".
    [Perhaps: EOD is signalled?]
  - Hey, this isn't quite like my CD player at home... 
    it keeps on playing forever!

Let's remedy this last problem:

Attempt 2:
   state  |   S/S     EOD      SOD   
----------+------------------------
 idle     |  play1     ??       ??
 play1    |  idle     rotate2   ??
 rotate2  |  rotate2   ??      play2
 play2    |  idle     rotate3   ??
 rotate3  |  rotate3   ??      play3
 play3    |  idle      idle     ??

"play1".."play3" are all just hooked up to the disc-spin motor,
and "rotate2", is hooked up to the carousel-rotate motor.

Okay this attempt is better, but still has problems.
 - What happens after listening to all discs, and then
   coming along and pressing Start/Stop?
   [Which disc is cued up? don't be mis-led by the state name!]
 - When we stop, (wait a day), and then start, which disc gets resumed?
   This might be the desired behavior, or might not be.

On your own: fix the first problem.



Got to here, 03.apr.17


(Not covered:)
 

 Now, add a toggle button rpt/rpt-all/seq/shuffle.
 Note that this requires more state, to remember which we're in.

 In particular, nearly an entire copy of our original machine.
 This is called the "cross-product construction".
   (At a high-level, this would of course be an awful program.
    In general you might consider adding variables in addition
    to state, but only judiciously -- else we could do everything
    with a big program and one state.
    Alternately, we could consider the "rpt" toggle as an input,
    which we ignore most of the time, 
    and make transitions like "EOD & rpt".
    How to avoid ANDing inputs?  Add an extra state (effectively computing AND)!




Further example:  Volleyball  [Moved to homework]
 Recall that only the serving side can score.
 State: currently need to serve, or return?  Which team just played?
     (optional: re-serve)
 Input from ref "successful hit" or "failed hit" (S,F) or "score updated".
 
 State that we'll ignore for this exercise:
   overtime (w/ rally points: any serve scores);
   ending the game (requires tracking the #points, an extension go FSM);
   3 hits on a side;
      That takes some extra input signals, 
      "failed hit, okay hit across, okay bump".






2004.Apr.tax:
Preview from next lecture, complexity:

Lemma: log(n) = Θ(n log n).
  [Show.]

A lower bound on sorting:
   (Rosen 9.2)
   computation tree based on comparisons; has n! leaves;
   thus must have height lg(n!) = Ω(n log n) 



2004.Apr.tax:
Finish up Fibonacci (the derivation of the homegeneous linear recurrence)