Ben Bitdiddle has designed an electronic lock with three buttons: "reset", "0" and "1". He has provided the following state transition diagram showing how the lock responds to a sequence of inputs.

The lock makes a transition from its current state to a new state whenever one of the three buttons is pressed and released. It ignores its inputs if more than one button is pressed. Pressing "reset" returns the lock to the state marked "R" in the diagram (arcs showing the transitions to the reset state have been omitted from the diagram to make it easier to read). Pressing "0" or "1" will cause the lock to follow the appropriately labeled transition from its current state. The lock opens if it reaches the state marked "U".

1. After pressing the "reset" button what is the length of the shortest sequence of button presses that will open the lock?

2. After pressing the "reset" button what is the length of the longest sequence of button presses that will cause the lock to open after the last button in the sequence is pressed but not open any earlier in the sequence?

3. After much use, the "reset" button breaks. Is it still possible to open the lock using only the "0" and "1" buttons assuming you know nothing about the lock's state (except that its locked!) when you start?

4. Suppose Ben wanted to design a lock that required exactly 10 button presses to open after pressing "reset". Not counting the "reset" and "unlock" states, what is the minimum number of state his FSM would need need?

A possible implementation of a finite state machine (not related to the lock above) with one input and one output is shown below.

1. If the register is N bits wide, what is the appropriate size of the ROM? Give the number of locations and the number of bits in each location.

2. If the register is N bits wide, what is the least upper bound on the number of states in a FSM implemented using this circuit?

3. What is the smallest value for the ROM's contamination delay that ensures the necessary timing specifications are met?

4. Assume that the ROM's tCD = 3ns. What is the smallest clock period that ensures that the necessary timing specifications are met.

An FSM, M, is constructed by connecting the output of a 3-state FSM to the inputs of an 9-state FSM. M is then reimplemented using a state register with the minimum number of bits. What is the maximum number of bits that may be needed to reimplement M?

You connect M N-state FSMs, each have 1 input and 1 output, in series. What's an upper bound on the number of states in the resulting FSM?

The following circuit diagram implements a FSM with two state bits, S0 and S1:

1. What is the smallest clock period for which the circuit still operates correctly?

2. A sharp-eyed student suggests optimizing the circuit by removing the pair of inverters and connecting the Q output of the left register directly to the D input of the right register. If the clock period could be adjusted appropriately, would the optimized circuit operate correctly? If yes, explain the adjustment to the clock period that would be needed.

3. When the RESET signal is set to "1" for several cycles, what state is the FSM set to? (Give values for S0 and S1.)

4. Assuming the RESET signal has been set to "0" and will stay that way, the state following S0=1 and S1=1 is

5. Now suppose there is skew in the CLK signal such that the rising edge of CLK always arrives at the left register exactly 1ns before it arrives at the right register. What is the smallest clock period for which the FSM still operates correctly?

Phil Harmonic, a reverse engineer at Irrefutable Logic, is trying to figure out a competitor's product. He has traced the circuit and diagrammed it as follows:

1. Phil suspects that the device is a finite state machine. What can you say about the number of states in the device?

Phil's analysis reveals that the truth table of the ROM is as follows:

Note that S1 and S0 are the two state bits held in the register and S1' and S0' are the "next state" register inputs computed by the ROM during each cycle. Although Phil doesn't completely understand the table, he notices that certain columns are identical to other columns in the table.

2. Complete the following state transition diagram for the device. Be sure to fill in all transitions, as well as output values for each state.
   

Frederick "Flip" Phlop, ILI's state machine specialist, claims that the ROM can be eliminated entirely for the competitor's finite state machine. Flip proposes the ILI's equivalent FSM can be constructed from two D Flip-flops with no additional logic.

3. Is Flip's claim correct? If so, support it by diagramming an equivalent FSM in the space below, using ONLY the given flops (and your added wires). Hint: Flip aced 6.004 and hasn't been wrong yet.
   

Each FPSM is "programmed" by connecting each of P00, P01, P10 and P11 to constants (logical 1 or 0). The next state value Q' is then computed from the input X and the current state Q. On power-up, the FPSM always starts out in the Q=0 state.

A proposed application of the FPSM device is to implement a clocked FSM called a TFlop whose state transition diagram is shown below:

1. What value of the P00 - P11 programming parameters, if any, generate the TFlop FSM behavior? If none, explain.

2. ESML's zealous director of marketing has drafted advertisements claiming that an FPSM chip can be used to implement ANY specified 2-state Moore Machine have 1 input and 1 output. Recall that a Moore Machine is an FSM whose outputs are a function of its state but not of its current inputs. Is the claim accurate?

Cass Kade, an ESML applications engineer, has discovered the following circuit using TFlops:

where the TFlop clock inputs are connected to a common clock source.

3. Give a state transition diagram for Cass's circuit. Label each state with the values of the state variables Q0 and Q1.

Cass proposed a second product constructed as follows:

Cass argues that supplying programming inputs to the two FSMs, a wide variety of 4-state, 2-output, 1-input Moore Machines can be implemented.

4. How many ways of programming Cass's proposed device are there? Ignore equivalence (i.e., count two different configurations which produce equivalent FSMs as two ways rather than one).

The director of marketing has been told that a general implementation strategy for a class of 4-state Moore Machines whose outputs are copies of state variables is the following:

5. Can marketing claim that EVERY 4-State Moore Machine which can be implemented using the above approach can be implemented by appropriately programming one of Cass's proposed devices? Explain.

You are probably aware of the classic problem of the farmer who must cross a river with a hungry fox, a hungry goose, and a bushel of cabbage. Unfortunately, the boat is only able to carry the farmer and one of his cargo items. However, if he leaves the fox and goose unattended, the fox will eat the goose. Likewise, if he leaves the goose and cabbage alone, the goose will eat the cabbage. The farmer's goal is to transport the fox, goose, and cabbage across the river intact.

Depict the river-crossing problem as a state transition diagram; be sure to show all possible states. Hint: the inputs to this state machine are the animal/cargo that is being taken across the river (M, F, G, or C) and the states indicate who is on which side of the river. Note that in the solution we won't want to transition to some of the states since they correspond to illegal pairings of cargo on one side of the river or the other.

How many bits of state are required to implement this diagram? How large of a ROM is needed to implement this state machine?

Given a vending machine that accepts quarters, dimes, and nickels as inputs and dispenses sodas when a total of at least 50 cents is deposited. Design a state machine that will accept coinage and dispense both sodas and change. The inputs to the system are Q, D, and N, RS, for quarter, dime, nickel, and request soda respectively. The outputs are DS (for dispense soda), RD (for return dime), and RN (for return nickel). Note that multiple states may be required to return all of the change.

Draw a state transition diagram for the specified machine. How does this diagram change if all extra money inserted, after the total required to purchase the soda is met, should to be considered as a tip. However, change should be dispensed at the point where the cost of the soda is initially reached.

The following two state machines have a single input, with a value of 0 or 1, and a single output indicated by a light that is turned on. The light being turned on is indicated by a state that is doubly circled. Can the two state machines shown below be distinguished from each other by merely specifying input sequences and observing the output? Write out a truth table for each implementation.