Consider the following puzzle: A farmer (F) with his wolf (W), goat (G), and cabbage (C) come to the left bank of a river they wish to cross. There is a boat at the river's edge that can carry at most two things across the river at a time, one of which must be the farmer. If the wolf is ever left alone with the goat, the wolf will eat the goat. If the goat is left alone with the cabbage, the goat will eat the cabbage. The puzzle is to come up with a sequence of river crossings so that all four characters arrive safely on the other side of the river.

One way to represent the states of this problem is with two sets, the characters on the left and right banks of the river respectively. For example: {F,G},{W,C} represents the farmer and goat on one bank, and the wolf and cabbage on the other. Answer the following questions using this state representation. Draw a state space diagram of the complete state space. Use the "{F,G}, {W,C}" style of labeling states. Indicate the initial and goal states. A couple of states are shown below.

Initial state