To get your participation credit, make sure you
upload your Definitions file to turnin before you leave the lab!
(This work will not be graded---full credit just for submitting.)
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.
Put your name in a comment at the top of the Definitions area.
Switch to "Beginner Student with List Abbreviations" for this lab.
There are three basic functions for building lists: cons, list, and append (concatenation). Their contracts are as follows:
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 DrRacket:
(cons empty empty)
(list empty empty)
(append empty empty)
(cons (list 1 2 3) (list 4 5))
(list (list 1 2 3) (list 4 5))
(append (list 1 2 3) (list 4 5))
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 this example small, we'll assume that a soda costs 25 cents and that the machine accepts only 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 cause 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. Computer scientists use these machines all the
time in their 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: You are going to write a series of programs to work with state
machines. Write the data definition for a list of transitions and the associated
template for functions on a list of transitions. Write the list of transitions for the soda machine example
showed above. Define it as the constant Write a function should produce Write a function should produce Everyone should be able to finish up to this point. Write a function 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 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 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 Racket yet and
argue why it is technically necessary.
; A transition is (make-transition string string string)
(define-struct transition (source label target))
;Example
(make-transition "5-cents" "nickel" "10-cents")
soda-machine.get-next-state that consumes a
state name, an action, and a list of transitions, and produces a state
name. The state name produced should be the target state of the first
transition in the list with the given state name and action as its
source and transition label, respectively. For example,
(get-next-state "10-cents" "dime" soda-machine)
"20-cents".get-state-sequence that consumes
a state name, 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)
(list "0-cents" "5-cents" "15-cents" "20-cents")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
Racket's built-in function member to check whether an
item is in a list. See the Help Desk for details.]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.]"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.]