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.
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