Become familiar with the notation of state machines and be able to describe the simple function of any machine with a state machine.
The study of deterministic methods of reasoning, beginning with deterministic finite automata.
A finite state machine is the most common construct in all of Computer Science. It is the basis on which the rest of computation is built.
A state machine is a collection of states and transitions between those states. Each transition is a description of what triggers the transition into the new state.
Here is an example transition from Happy state to Sad state and back:
Sometimes it is useful to think of the transitions as events. Other times it is useful to think of them as "input consumed".
All computable problems can eventually be decomposed into state machines, but programming languages offer features for us to conveniently not need to code everything up as a state machine.
State machines often have a special start state (denoting where to start) and one or more terminal states (when to end).
The Greek letter ε (epsilon) is used to denote an state transition for which no event is required (or no input consumed) for the transition to take place.
State machines are frequently used explicitly in a number of programming situations.
- Network protocols
- Terminal emulators
- Web login systems
- Compilers
- Game AI
Anyplace state needs to be maintained, a state machine is of use.
The soda machine takes any combination of nickels, dimes, or quarters to reach $0.25, then dispenses a soda.
(Error states omitted for brevity, e.g. what happens if the user puts in a dime and then a quarter?)
Notice how the addition of each coin moves us to the next state (which is the total value deposited so far). Or put another way, how the consumption of the next input moves us to the next state.
Follow the state machine as the user deposits a dime, a nickel, and then another dime.
Video game AIs can exist in a lot of states, e.g. idling, bored, running, shooting.
- Come up with a list of 4 states an AI can be in.
- Figure out the transitions between those states.
- Draw a state machine diagram of your AI.