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