A finite state machine (FSM) is a simple machine that moves through states as time elapses. The word 'machine' is used loosely here to mean an abstract representation of a process. In this sense the act of reading a sentence and understanding its meaning is to submit inputs to the machine we call the brain.
A FSM moves from one state to another as the result of receiving a particular input. Inputs are typically single characters or 'tokens' (groups of characters such as words). A simple machine would be one with a few states and two inputs, A and B. The next state is determined by the input, from state 1 input A might lead to state 2 while input B might lead to state 4. In some states only one of the inputs may be valid. In more advanced machines there may be multiple inputs, A, B, C, D, etc.
A FSM must also have a memory of its current state because this may determine its next state. A FSM may change to state 1 if it receives input A and input 2 if it receives input B.
A simple example of a finite state machine is a ball point pen. How many states does a ball point pen have? What are the possible inputs to a ball point pen? What memory of states is required by a ball point pen. We can write these into a state table for the ball point pen:
| State | Input: |
| 1: | |
| 2: |
A more complex finite state machine is a lift. What are the states of a lift? What are the possible inputs into a lift? What memory of states is required by a lift? Can we draw a state transition table for a simple lift? (Ground and first floor only.)
| State | Input: | Input: |
| 1: | ||
| 2: | ||
One example might be a light bulb that has either two states (on/off) or more than two (off, dim, medium, bright, etc.) A state table (or state transition table) holds the rules for changes in the state of the automaton, for example a bulb in the off state can react to a message to turn on.
Another example might be a coin tossing machine that produce sample output like this:
h h t h h t h h h t t h h h h t t h t t t h h h h h t h h h t t t h h h t t t h h h h h h h t t h t t t t t h...
The state table can be represented by a diagram. Is the coin tossing machine a fair one or is it biased? Given the sequence [h h t h] would you put your house on the next coin toss? What about [t t h t]? Is the machine a fair one? Can you draw a FSM for a fair coin tossing machine?
Following a path through a state table is similar to tracing a route on a map, moving from place to place or symbol to symbol according to a list of instructions.
A state table might hold the instructions for moving across a map to locate some treasure. The instructions don't say 'go straight to point X', that would be too easy, instead they list a series of places with the correct route listed as a series of steps. Each point in the state table provides two options, A and B. To find the treasure you must pick the correct route from the current point to take you to the next. Your movements from one place to another can be represented as a string of your choices, for example AABBBABAAB. This string is, like the parts of a sentence, an example of valid input if it results in the successful completion of the FSM. Invalid input will not be processed successfully by the FSM.
We can now have a go at a practical exercise, finding Treasure Island. There are 7 islands, represented by people around the room (teacher is Treasure Island). Each island provides two options to move to a new one, which are called options A and B. You start at Pirate's Island and ask for a route A or B. Mark the route you have chosen on your map and move to the island/person you have chosen. Write down the sequence of choices you make at each point so you have a string like this: AABBA, etc. Repeat these steps until you reach Treasure Island and claim your prize.
At the end of the practical work you should have your sequences of As and Bs to see how you managed to arrive at Treasure Island.
This idea might serve as the basis of an outdoor treasure hunt. Perhaps you could devise a game of your own that would take far longer to complete!