Library

DFA · Regular

Exact change: 30¢ in nickels, dimes and quarters

n is 5¢, d is 10¢, q is 25¢. The machine accepts the coin sequences that add up to exactly 30¢ — the states are the running total, and overpaying has nowhere to go.

0¢5¢10¢25¢15¢30¢20¢ndqndqndnndnd
The machine as drawn — 7 states, 13 transitions.Every word up to length 5, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

nq → acceptddnn → acceptndnnn → acceptnnnnnn → acceptdq → rejectndnn → rejectddnnn → rejectdnnnnn → reject