# CS 1102: Lab 2

## Lab Motivation and Goals

This lab is designed to help you practice programming over lists of structures. It also sets up a problem that we will use again in the second half of the course.

## Warm up: the various list operators

You've now seen three operators for building lists: cons, list, and append. Their contracts are as follows:

• cons : alpha list[alpha] -> list[alpha]
• list : alpha ... alpha -> list[alpha]
• append : list[alpha] ... list[alpha] -> list[alpha]

For each of the following expressions, try to predict (a) what they will return and (b) what the length of the resulting list is, then check your answers in DrScheme:

1. `(cons empty empty)`
2. `(list empty empty)`
3. `(append empty empty)`
4. `(cons (list 1 2 3) (list 4 5))`
5. `(list (list 1 2 3) (list 4 5))`
6. `(append (list 1 2 3) (list 4 5))`

## Exercises on lists of structures

Computer scientists and computer engineers frequently describe systems as finite-state machines (also called finite-state automata). The best way to understand a finite-state machine is through an example.

Imagine that you want to show how a soda/vending machine behaves. To keep the example small, we'll assume that a soda costs 25 cents and that the machine accepts nickels and dimes. The machine will not give change. The following figure shows the state machine:

• The circles are called states. Each state corresponds to an amount of money that has been deposited into the machine. The state corresponding to the amount of money deposited at any time is called the current state). The bold arrow marks the state to use as the first current state. In this case, the machine starts with no money.

• The arrows between states are called transitions. Transitions show what actions have to happen for the machine to go from one state to another. For example, if the machine currently has 5 cents and a nickel is deposited, then the machine has 10 cents. The labels on each state (here, nickel and dime) are the "actions" that the machine can react to.

(The soda machine is a trivial example. In reality, state machines are used to capture all sorts of systems, many with more than 2 to the power of 500 states. Professor Fisler uses these machines all the time in her research.)

If we give a name to each state, we can represent a state machine as a list of transition structures. A transition structure consists of three pieces of information: the name of the states on either end of the arrow and the label on the arrow. For example:

```    ; A transition is (make-transition string string string)
(define-struct transition (source label target))

;Example
(make-transition "5-cents" "nickel" "10-cents")
```

You are going to write a series of programs to work with state machines.

1. Write the data definition for a list of transitions and the template over a list of transitions.

2. Write the list of transitions for the soda machine example showed above. Define it in a constant called `soda-machine`.

3. Write a function `get-next-state` that consumes the name of a state, an action, and a list of transitions and produces the name of a state. The produced state should be the target state of a transition with the input source state name and action.

4. Write a function `get-state-sequence` that consumes the name of a state, a list of actions, and a list of transitions and produces a list of state names. The produced list should show the sequence of states visited while processing the list of actions (in order), starting from the given state. For example,

```  (get-state-sequence "0-cents" (list "nickel" "dime" "nickel") soda-machine)
```

should produce `(list "0-cents" "5-cents" "15-cents" "20-cents")`

5. Write a function `gets-soda?` that consumes a list of actions and produces a boolean indicating whether that sequence of actions visits the "soda" state. [Hint: the trick to this problem lies in breaking it down into appropriate helpers. You may use Scheme's built-in function `member` to check whether an item is in a list. See the help desk for details.]

Everyone should be able to finish up to this point.

6. It is possible to define state machines with multiple transitions with the same source state and same action but different target states (such machines are called non-deterministic). Write a function `find-non-det-states` that consumes a list of transitions and produces a list of names of source states that have multiple target states for the same action. [Hint: sort the list of transitions by source state and action as part of your solution.]

7. This definition of state machines relies on matching state names to hook up the transitions. If you made a typo when entering a state name (say "5-cts" instead of "5-cents"), you would create a machine in which there is no transition out of some state. Programs can help check whether such errors exist in a list of transitions. Write a function `dead-end-states` that consumes a list of transitions and produces a list of names of target states out of which there are no other transitions. [Hint: extract lists of the names of the source and target states from a list of transitions as part of your solution.]

8. It would seem that the problems with typos in the previous problem would go away if we made a structure for each state (containing its name and outgoing transitions), then put the state structure instead of the state name as the "target" of each transition. Why didn't we set the problem up this way? Consider what you would need to do this that you haven't learned in Scheme yet and argue why it is technically necessary.