Library

DFA · Regular

Measuring 4 litres with 3- and 5-litre jugs

Fill, empty or pour one jug into the other until it is empty or the other is full. A state is how much each jug holds, and the machine accepts when the large jug holds exactly 4. The shortest solution takes six moves.

0,03,00,53,50,33,23,30,21,52,01,02,50,13,43,10,4
The machine as drawn — 16 states, 96 transitions.

The author’s examples, run

fillB BtoA emptyA BtoA fillB BtoA → acceptfillA AtoB fillA AtoB emptyB AtoB fillA AtoB → acceptfillB BtoA emptyA BtoA fillB → rejectfillA fillB → rejectfillB emptyB → reject