State Machines:
Models for Designing and Implementing Programs
Here's a brief outline of the lecture (still under construction).
- What is a State Machine?
- Definition...
Technically, called an automata. Actually, a "finite" automata,
because it has a finite number of states. Two main types:
- Deterministic Finite Automata (DFA)
Exactly one transition from a given state, for a given event.
Unambiguous.
- 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.
- Parts:
- States (hence, "state machine")
- Events/Inputs/Symbols
- Outputs/Actions/Transitions
- Limitations
- No memory
- No "action" - Most actual implementations will allow code
to be executed upon a state transition.
- Variations (most exist to try to overcome limitations)
- Turing machine: state machine with virtual "tape drive"
- "Pushdown Automata": state machine with a stack memory
- How to implement?
- Nested If's... used by people who don't realize they're implementing
a state machine. Very similar to next technique...
- Nested switch()...
e.g. outer switch is state, inner switch event.
Main advantage: Simplicity.
- Table of function pointers:
- Dense (indexed by state and event)
- Sparse (each entry in table
specifies which state/event combo it's for)
- State machine language:
- Outputs one of above implementations (or similar)
- Examples:
- SMDL
- Flower
- How used?
- Parsing computer (or natural) language. Examples
from Dragon Book.
- Network protocol. Examples from X.25
and LAPB specifications.
- GUI. Example from Amiga program.