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).

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.

Encode the states in the above DFA with the 3-digit
binary representations of their labels.
We encode the transition characters with their
values, since they are single-bit quantities already.
Then the following table represents the I/O behavior
of our NeuroToast circuit:

Old State    Input     New State
---------    -----     ---------
  vwx          y          stu     <-- bit names

  000          0          001
  000          1          000

  001          0          010
  001          1          011

  010          0          010
  010          1          010

  011          0          100
  011          1          011

  100          0          010
  100          1          101

  101          0          110
  101          1          101

  110          0          010
  110          1          110

  111          0          don't care
  111          1          don't care
  
This table leads to the following Karnaugh maps, which have
simplified representations of

  s:  vx + vy + wxy'
  
  t:  vy' + wx' + wy + v'w'x
  
  u:  v'w'x'y' + vw'y + xy
  
  The circuit is left to the ambitious reader (or test taker).