Library

DFA · Regular

Missionaries and cannibals

Three missionaries and three cannibals must cross a river in a boat that holds two, and the cannibals may never outnumber the missionaries on either bank. A state is how many of each are still on the starting side and where the boat is; the shortest accepted word is the classic eleven-crossing solution.

33L32R31R22R32L30R31L11R22L02R03L01R11L02L00R01L
The machine as drawn — 16 states, 34 transitions.

The author’s examples, run

CC C CC C MM MC MM C CC C CC → acceptMC M CC C MM MC MM C CC M MC → acceptCC C CC C MM MC MM C CC C → rejectMM M → rejectCC CC → reject