Library

FST · Rational transduction

A vending machine that gives change

A drink costs 15¢. Nickels n and dimes d go in; when the total reaches 15 the machine prints V for the drink and, if it was paid 20, an n of change, and starts again. A Mealy machine could only answer one symbol per coin — here one coin can produce a drink and a coin together.

c0c5c10n/d/n/d/Vn/V, d/Vn
The machine as drawn — 3 states, 6 transitions.

The author’s examples, run

d → rejectn → rejectdd → reject · Vndn → reject · Vddd → reject · Vnnnddnnndddddnndd → reject · VnVVnVnVnVn