| |
DescriptionA demonstration of the (famous) man-wolf-goat-cabbage problem,
modelled and solved via a finite state machine.
The idea is taken from my German edition of the Hopcroft-Ullmann
classic Introduction to Automata Theory, Languages, and Complexity.
As such, the German naming convention
(Z for 'Ziege'='goat') and (K for 'Kohl'='cabbage') has been used.
The problem is stated as such: A man (M) has got a wolf (W), a goat (Z) and a cabbage (K). He wants to cross a river in his boat, which is so small that he can either go over alone (M) or carry at most one of the (W,Z,K) with him. Naturally, when unobserved, the wolf will eat the goat, and the goat will eat the cabbage. Is there a sequence of boat movements that allows the man to transfer all three items across the river?
Please open the state-machine editor (popup-menu, edit) to see solution for the problem modelled as a finite state machine. This is actually a complete solution of the problem that covers all possible sequences of boat movements, including the infinitely many suboptimal sequences which contain useless loops.
The name of each state encodes the current situation,
with the items on the left and right bank of the river
separated by a minus sign.
For example, the state name MWK - Z indicates that the man, wolf,
and cabbage are on the left bank, while the goat (Z) is on the right bank.
Using this convention,
the starting state (at the top) is called MWKZ - 0,
and the target state (at the bottom) is called 0 - MWKZ.
The transitions are labelled with the items carried during the
corresponding boat movement, e.g. W & !(M|Z|K)
indicates the man taking over the wolf.
To avoid too many crossing transition arrows,
two separate ERROR states (on the left and right) are used.
These are reached whenever something goes wrong
(like the goat eaten by the wolf).
The 'accept' output of the state-machine indicates that a final state
(either the solution or an error state) has been reached.
Click the input switches or type the 'c' and 'm','w','z','k' bindkeys to control the clock input and select the four possible transitions. Note that only one of the four 'm','w','z','k' inputs should be selected, but that is not enforced by the circuit. It would have been possible to auto-generate the clock pulses from the input switches for easier typing, but the realization shown here allows you to see the active transition during the simulation, which makes solving the problem much easier.
Run the applet | Run the editor (via Webstart)