CS60 final fall 99

5. (DFAs and their implementation) [50 points total]

Having succeeded with ToastBoost®, you are approached by several of ToastRWealth's forward-looking engineers about "NeuroToast," an experimental, artificially intelligent toasting system. NeuroToast will revolutionize toasting by determining -- without human intervention -- whether or not a particular slice of bread has been toasted to specification. Further, NeuroToast is touted to be platform-independent, in that it works with any toasting appliance. The idea is that NeuroToast will measure an appliance's ambient toasting temperature and determine at each time step whether that temperature is correct.

Though still working out the details of what constitutes a "correct" temperature, the engineers have decided that a toasting session will be considered a failure if

In the sequence of measurements, two or more incorrect temperatures are sensed consecutively OR
In the sequence of measurements, four or more incorrect temperatures are sensed (regardless of whether they are consecutive or not).

Otherwise, the toasting session would be considered a success.

Your task is to design a sequential circuit that, at the end of a sequence of binary inputs (0 indicates an incorrect temperature; 1 indicates a correct temperature), outputs whether or not the toasting was unsuccessful by the above criteria.

(A) (20 points) Create a DFA (deterministic finite automaton or deterministic finite-state acceptor) that accepts binary input sequences that encode unsuccessful toasting sessions. The DFA should reject successful toasting sessions. (Hint: one possible way to think about the each state in your DFA is to consider that it represents a pair of values: (1) the number of consecutive 0's seen and (2) the total number of 0's seen.)

(B) (30 points) For the finite-state machine you constructed in part (A), create a simplified (sequential) switching-circuit implementation. Make the logic as simple as you can. The encoding of the DFA's states is up to you. Your circuit will output 1 (high) on unsuccessful toasting sequences and 0 (low) on successful toasting sequences.