State Machines:
Models for Designing and Implementing Programs

Here's a brief outline of the lecture (still under construction).

  1. What is a State Machine?
    1. Definition...
      Technically, called an automata. Actually, a "finite" automata, because it has a finite number of states. Two main types:
      1. Deterministic Finite Automata (DFA)
        Exactly one transition from a given state, for a given event. Unambiguous.
      2. Non-Deterministic Finite Automata (NFA)
        May have a transition out of a state for no event (i.e. spontaneously), or more than one possible transition for a given event. An NFA may be converted to a DFA (effectively, the DFA has a state for every possible state combination the NFA could be in.
    2. Parts:
      1. States (hence, "state machine")
      2. Events/Inputs/Symbols
      3. Outputs/Actions/Transitions
    3. Limitations
      1. No memory
      2. No "action" - Most actual implementations will allow code to be executed upon a state transition.
    4. Variations (most exist to try to overcome limitations)
      1. Turing machine: state machine with virtual "tape drive"
      2. "Pushdown Automata": state machine with a stack memory
  2. How to implement?
    1. Nested If's... used by people who don't realize they're implementing a state machine. Very similar to next technique...
    2. Nested switch()... e.g. outer switch is state, inner switch event.
      Main advantage: Simplicity.
    3. Table of function pointers:
      1. Dense (indexed by state and event)
      2. Sparse (each entry in table specifies which state/event combo it's for)
    4. State machine language:
      1. Outputs one of above implementations (or similar)
      2. Examples:
        1. SMDL
        2. Flower
  3. How used?
    1. Parsing computer (or natural) language. Examples from Dragon Book.
    2. Network protocol. Examples from X.25 and LAPB specifications.
    3. GUI. Example from Amiga program.