Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 57 ยท Projects

Project: Vending Machine Controller

Design a vending machine controller as a finite state machine. Build the state diagram and table, add change and refund, then test it with sequences in Python.

A vending machine is the textbook example of a finite state machine. It has a small memory (how much money has been inserted), it reacts to a stream of events (coins, a refund button), and it produces outputs (an item, change). Nothing else is needed, so it is the ideal project for practicing the design flow from Finite State Machines and Designing a Sequential Circuit.

In this project you will specify the controller, draw its state diagram, turn it into a state table, simulate it in Python, and test it two ways: with hand-picked sequences and with thousands of random ones that check that no money ever disappears.

Step 1: specify the machine

Our machine sells one item for 15 cents. It accepts only nickels (5 cents) and dimes (10 cents). It has a refund button. It does not keep any extra change: if you overpay, it gives the excess back immediately. Each clock tick, the machine reads one input symbol:

  • N: a nickel was inserted
  • D: a dime was inserted
  • R: the refund button was pressed
  • -: nothing happened

The outputs are DISPENSE (release the item), CHANGE 5 (return a nickel) and REFUND n (return the credit of n cents).

Ingredients of the controller

Inputs Nickel, dime, refund, idle.
State Credit so far, 0, 5 or 10 cents.
Outputs Dispense, change, refund.

The price is 15, so credit never needs to reach 15.

1 / 2

The key design decision is that the machine does not need a "credit 15" state. As soon as the credit would reach 15 (or more), the machine dispenses and the state goes back to 0 within the same transition. The output therefore depends on both the state and the input, which makes this a Mealy machine. A Moore version would need extra "dispensing" states to carry the output.

Step 2: the state diagram

In the diagram, an arrow label N / DISPENSE means "on input N, produce output DISPENSE". The idle (-) self-loops and the refund button in state 0 are left out of the picture to keep it readable, but they appear in the table below.

stateDiagram-v2
    [*] --> S0
    S0 --> S5: N / -
    S0 --> S10: D / -
    S5 --> S10: N / -
    S5 --> S0: D / DISPENSE
    S5 --> S0: R / REFUND 5
    S10 --> S0: N / DISPENSE
    S10 --> S0: D / DISPENSE + CHANGE 5
    S10 --> S0: R / REFUND 10

State diagram of the vending machine controller. S0, S5 and S10 are the credit in cents.

Step 3: the state table

A diagram is good for people. A state table is complete and mechanical: one row for every combination of state and input. Four inputs and three states give 12 rows, and a missing row would be a design bug, which is why a table is safer. In Python the table is simply a dictionary from (state, input) to (next state, output).

Python The complete state table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the table against the specification, row by row. A nickel in state 5 moves to 10 without output. A dime in state 5 makes 15, so it dispenses and goes back to 0. A dime in state 10 makes 20: the machine dispenses and returns a nickel. The refund button gives back exactly the credit held in the state.

Step 4: the simulator

The machine itself is tiny: it stores the current state and looks up the next state and output in the table. This is the table-driven style, and it is the reason finite state machines are easy to verify. The code below runs a list of test sequences and compares the outputs and the final state with what you expect from the specification.

Python Running test sequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each test is a small story. NDD inserts a nickel and a dime (15, so it sells), then a second dime, which starts a new purchase with 10 cents of credit. NNNN buys one item with the first three nickels and leaves the fourth nickel as new credit. D--D shows that idle ticks (-) do not change anything.

Step 5: test it harder

Hand-picked examples catch the bugs you thought of. To catch the others, check an invariant, a statement that must be true for every possible input. For a vending machine the invariant is conservation of money:

money inserted = 15 ร— items sold + change returned + refunds + credit still inside

The program feeds 2,000 random input sequences (with a fixed random seed, so results are repeatable) and checks the invariant for each. It also explores the table to list which states are reachable from the start.

Python Random testing with a money invariant

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No sequence breaks the invariant, and all three states are reachable, so there are no dead states in the table. Try breaking the machine on purpose: change the output of (10, "D") to "DISPENSE" without the change, and run the program again. The invariant check fails immediately, which is the point of testing against an invariant: it finds the bug without you having to guess which sequence triggers it.

Step 6: from table to gates

To build the controller in hardware, follow the steps of Designing a Sequential Circuit:

  1. Encode the states with two flip-flops: for example S0 = 00, S5 = 01, S10 = 10. The code 11 is unused. It is a source of don't-cares for the logic, and you should add a safe path back to S0 for it, as discussed in State Machine Patterns and Pitfalls.
  2. Encode the inputs with two bits, say 00 idle, 01 nickel, 10 dime, 11 refund.
  3. Write the next-state and output tables with state and input bits as variables (four variables in all) and simplify each flip-flop input and each output with K-maps.
  4. Add the clock and a reset so the machine starts in S0.

The software model and the gate design are the same machine. The table is the single source of truth, and the Python version lets you verify it before building anything.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is this vending machine a Mealy machine?

    DISPENSE appears at the moment a coin completes the price, as a function of the state and the coin. A Moore machine would need extra states to show the same output.
  2. 2. How many rows does the complete state table have?

    There are three states and four input symbols (N, D, R and idle), so 3 x 4 = 12 rows. Every combination must be defined.
  3. 3. What happens when a dime is inserted in the 10-cent state?

    10 + 10 = 20 cents, which is 5 more than the price. The machine dispenses and returns the 5-cent excess, then goes back to the 0 state.
  4. 4. What does the money invariant test check?

    Money in must equal 15 times the items sold plus change, refunds and the credit still held. If any transition loses or invents money, the equation fails for some sequence.
  5. 5. Why is a table-driven simulator easy to verify?

    All the behavior lives in the table, which can be reviewed against the specification. The code that runs it is a few lines that rarely hide bugs.

Summary

  • A vending machine controller is a finite state machine: credit is the state, coins and buttons are the inputs, and items and change are the outputs.
  • Because the output depends on the state and the input together, this controller is a Mealy machine. It needs just three states since reaching the price returns to 0 at once.
  • A complete state table has one row for every state and input pair, and it is the single source of truth for both simulation and hardware design.
  • A table-driven Python runner makes the machine easy to test with sequences, and an invariant such as "money in equals money accounted for" checks thousands of random runs.
  • The hardware design follows the standard flow: encode states, write next-state and output tables, simplify with K-maps and add a reset.

Next: Project: A 4-bit ALU with Register File.