Library

DFA · Regular

Wolf, goat and cabbage

A farmer must ferry a wolf, a goat and a cabbage across a river, one at a time, never leaving the wolf with the goat or the goat with the cabbage. f crosses alone; w, g, c take that passenger. The accepted words are the solutions; the two shortest take seven crossings.

FWGC|·WC|FGFWC|GC|FWGW|FGCFGC|WFWG|CG|FWCFG|WC·|FWGCgfgfwcwggcgcwgfwcfgg
The machine as drawn — 10 states, 20 transitions.

The author’s examples, run

gfwgcfg → acceptgfcgwfg → acceptgfwgcfgfg → rejectgfwfg → rejectfgwgcfg → rejectwfgcfwg → reject