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.
The author’s examples, run
gfwgcfg → acceptgfcgwfg → acceptgfwgcfgfg → rejectgfwfg → rejectfgwgcfg → rejectwfgcfwg → reject