# State Diagram study problems

### Problem 1

Suppose we have a state diagram with n states
and k different actions.
In how many different ways could we construct a transition
function for this diagram?

hints

solution

### Problem 2

Recall that a phone lattice is a type of
state diagram, i.e. a directed graph where each node represents
a state of a system. A phone lattice has exactly one
letter on each edge. Each path from the
start node to a final/end node represents a word. Draw a phone
lattice representing exactly the following set of words, using a single
start node and no more than 9 nodes total.

bat, back, sat, sack
boo, booo, boooo, ... [i.e. b followed by two or more o's]
moo, mooo, moooo, ... [i.e. m followed by two or more o's]

solution

### Problem 3

Suppose we're modelling an RC crane which is receiving a sequence
of input commands, each of which is UP, DOWN, or BEEP.
This crane has only two vertical positions, and starts in the high
position. It should go into
an ERROR end state if it is asked to go UP when it is in the high position
or DOWN when it is in the low position.
Once it is in the ERROR state, it stays in the ERROR state no matter
what commands it receives.
BEEP commands are legal at any point.
Give a state diagram for this system, in which each edge
corresponds to receiving a single command.

solution