High School Computer Science and Programming Workshop
Class 13: State Machines


Hesam Samimi, Cliff Kushler
Ananda Living Wisdom School



Here is a direct link to Snap!


To play with Snap! you can just click on the play button on some of the images, like the one above. If you have any problems with it loading, visit Snap! directly in a new browser tab (On that page, click "Run Snap! now"). Another possible solution, if your browser is not Chrome, is to give Chrome a try.


The Vending Machine

Vending Machines. You probably have one in your school. Simple things right? They are indeed. But even so they still have a whole system. For example, if you go to one and start pressing the selection buttons, nothing will happen. That's because you've not yet inserted any money. Let's imagine you've been asked to design a vending machine. As we learned before, the first step is to build a model for how its system should work. How would you model this machine?

Thinking about this a bit, we will soon realize that the vending machine behaves differently, depending on which stage, or sometimes called state, it is in:

Computer theorists have come up with a mechanism to model such machines that behave differently depending on the state they are in. They call it a State Machine.

We draw a state machine using circles for states and arrows connecting the circles to represent actions or transitions between those states. A transition is labeled by the name of an input which triggers it, and maybe also an output that the machine produces upon taking that action/transition. For example, here is a representation for a simple vending machine selling soda cans, which say all have the same price of $1:

Lots going on here! Let' go over them. As you see, we have only 2 states (the purple circles). One is labeled "WAIT FOR ENOUGH MONEY", representing the state when the machine is idle or still needs more coins or cash inserted to reach the price of each can: $1. Note that this state is marked as the Start state, indicating that this state is where the vending machine is, when we begin interacting with it.

Sometimes a start state indicator or a transition can be labeled with an action. Here our start state indicator has a label, saying we should start by setting a variable called TOTAL to $0. This variable will tell us how much money is inserted into the machine at any given point.

Now notice that there are 2 transitions (gray arrows) that originate from this state. The one with the arrow going into the state itself (at the bottom center) indicates a transition which has an action, but does not change the state.

A transition is often represented using the notation input / output. Sometimes there is also a condition, which indicates only to take the transition and action if the input has arrived AND the condition is true. I am indicating this situation with the notation input / condition / output.

This first transition is labeled as: "CASH / if TOTAL + CASH < $1 / Change TOTAL by CASH". So what triggers this transition is when the input CASH has been received (customer just inserted this much money in coin or bill) AND the condition TOTAL + CASH < $1 is true.

For example, let's say we just go to the machine (so TOTAL = $0) and insert a nickel (5c). Because $0 + $0.05 < $1 is true, then both input and the condition are met and so the transition is taken, following the arrow, which keeps the state as before, but also performs the action "Change Total by CASH". Thus we get TOTAL = $0.05.

The other transition (on top) has the same input ("CASH"), but will not get triggered because the condition TOTAL + CASH ≥ $1 is not true. A properly designed state machine will never allow two different transitions to happen at any given point!

Let's say the customer just realizes he has no more coins, so he next inserts a $5 bill.

This time the top transition will get triggered, as the input ("CASH") is met as well as the condition TOTAL + CASH ≥ $1 since TOTAL + CASH will equal to $5.05 at that point.

Therefore its action "Change Total by CASH" will be taken, setting TOTAL to $5.05, and then the transition will take the machine to the second state, marked "WAIT FOR SELECTION".

At this state, notice that the machine only accepts one kind of input: Selection Made, meaning the customer presses one of the buttons to choose the item he wants. Since there state machine does not take the CASH input here at this state, this means the vending machine will not let the customer insert new money at this point.

Notice the transition from this state: "Selection Made / Dispense Product, Dispense Change: TOTAL - $1, Set TOTAL to $0". It has an input and a list of outputs (actions), but there are no conditions. So when the customer selects a product, one quantity of that product is dispensed, as well as any change (in our example $4.05), and then TOTAL is set back to $0, and the machine goes back to the first state, waiting for the next sale.


Exercise: Traffic Light

Can you draw the State Machine for the traffic light we saw in Class 6? It started in green. Remained in green for 10 seconds, then went to yellow, for 3 seconds, and then red for another 10 seconds, then back to green.


Exercise: ATM

Can you draw the State Machine for the simple ATM we saw in Class 5?


Next: Class 14: Internet Protocols
Previous: Class 12: Propositional Logic, "Have I Lied?" Game
Back to: Table of Contents