2. With this exercise we shall develop a solution to the following riddle. Alice, Bob, Carol and Dave want to cross a bridge in the dark of night. However, the bridge is rigged with a bomb which is due to explode, destroying the bridge, in 17 minutes. They have one flashlight which must be used when crossing the bridge, but the bridge can hold only two people at once. Their walking speeds allow them to cross in 1, 2, 5 and 10 minutes, respectively; when two of them cross together, they must walk together with the flashlight. How can they all get safely across the bridge? To solve this riddle, we shall model it using an appropriate labelled transition system (LTS).

(a) What would the states of your LTS consist of? Make sure you consider all the aspects of the riddle. Justify your notion of state.

(b) What are the actions of your LTS? List all the actions. Justify your choice of actions.

(c) Drawing out the entire LTS may be a time consuming task as there could be very many states and transitions. However, drawing out only part of the LTS is doable. Draw part of the LTS, anywhere between 6 and 12 states, including the starting state. Label the states so that it is clear what the states represent, and explain your labelling.

(d) Solve the riddle. Provide a sequence of transitions (listed or drawn) that solves the riddle. [10 marks]