Your name __________________________

CS 60 Seqential Logic Worksheet

1 problem -- lots of parts -- 50 points




This worksheet is due by midnight on Friday night, May 10



1. [50 points] (CS60 meets Krispy Kreme donuts)

When Scott Livengood, the president of Krispy Kreme Donuts, hears that you have taken CS 60, he decides to make it worth your while (in free goods) to help improve the quality-control systems for the franchise's donuts.

As CEO Livengood explains, even on a slow day the Krispy Kreme staff are too busy to thoroughly check the donuts before packing them off to their swarms of customers. As a result, stores have been receiving complaints that their donuts' holes are often too large or too small. Krispy Kreme has purchased a sensor to help with the quality-checking of the donuts, and they would like you to design an automatic system to do that quality-checking.

Under the middle of their donut conveyor belt, Krispy Kreme has installed a heat sensor that checks (every so often) whether or not a donut is passing directly above it. If, in fact, the dough of the donut is passing by, the sensor returns a '1'. If, on the other hand, the donut hole (or no donut at all) is passing over the sensor, the sensor returns a '0'.

Before a donut has reached it, the sensor will measure an initial sequence of 0's. (Thus, there may be zero or more 0's in this initial part of the sequence.) These initial 0's (if any) turn to 1's as the leading edge of the dough hits the sensor. When the donut hole is passing overhead, more 0's will appear, and then the trailing half of the donut will trigger more 1's. Once the donut has completely passed by, the sensor produces a trailing sequence of zero or more 0's.

The following are four example sequences (A) through (D) of measurements that might occur as a donut passes over the sensor, along with a description of the donut that created them. 

(A)   0 1 1 1 0 0 1 1 1 0 0             (a thick-dough donut)

(B)   0 0 0 0 1 0 0 1 0 0 0 0           (a premium donut -- see below)

(C)   0 1 1 0 1 0 1 1 0 0 0 0           (a donut with two small holes)

(D)   0 0 1 0 0 0 0 0 1 0 0             (a donut with a very large hole)

After several intense days of taste-testing, you decide that only donuts whose holes register TWO or THREE '0' measurements are good enough to earn Krispy Kreme's premium status. Other donuts will be considered "seconds" and sold to supermarkets. Further, in order to be "premium," a donut can not be too thick -- that is, the donut's leading and trailing edge of dough can only register a single '1' measurement. There can be any number of leading or trailing zeros. Thus, example donut (B) above is a premium donut; examples (A), (C), and (D) are not. You should assume that premium donuts have to have exactly one hole.

Part A. [5/50 points] (DFAs)

Draw a DFA (Deterministic Finite Automaton) that accepts sequences of measurements for premium donuts and rejects any other sequences of measurements. (After each accepted premium donut, you can assume the machine will get reset by some external mechanism, so don't worry about handling more than 1 donut.)

Be sure your machine rejects donuts (A), (C), and (D) in the above example. It should accept donut (B).




















Part B. [5/50 points] (truth tables)

Convinced that premium donuts are the future of the industry, Krispy Kreme asks you to implement your premium-donut detector (the DFA from part A) in hardware.

First, choose a binary representation of the states of the DFA you created in part A. Then, create a truth table of inputs and outputs that describes the operation of your DFA. Be sure to label the names of your bits clearly. (Hint: if you had more than 8 states in your DFA, you may want to go back and redesign it to have fewer states.)



































Part C. [15/100 points] (Karnaugh maps)

Continue with your hardware design by plotting the values from part B's truth table (input/output table) on Karnaugh maps. Then, write the simplified sum-of-products form that describes each output bit's logical function. Keep in mind that you may have "don't care" vertices in your Karnaugh maps.

Several Karnaugh maps are provided below (that doesn't mean you will need all of them -- depending on your DFA, you may not even need a 4-bit (16-vertex) K. Map). The decimal numbers correspond to the values of each vertex if the bits are ordered wxyz from most- to least-significant.




                       





                       







Part D. [5/50 points] (circuits)

On the back of the previous page sketch a circuit that implements your premium-donut detector. (If you need to sketch it elsewhere, please indicate where we should look... .)







Part E. [5/50 points] (regular expressions)

As your premium-donut detector gains renown, it prompts the big donut conglomerates (Hostess, Entenmann's) to approach you about creating a "batch-mode" version of your machine.

What they would like to do is to collect all of a day's donut measurements into a file (one measurement sequence per line), and then, at night, sift through this file to find out which of the day's donuts qualify as "premium". They would like to use regular-expression matching (for example, with Unix's grep or egrep commands) to accomplish this. In addition, they hope to use this method to get rid of any donuts that do not have exactly one hole before packaging.

Create two regular expressions: the first should match the measurement sequences of premium donuts (but no other measurement sequences). The second regular expression should match only the measurement sequences of donuts that do not have exactly one hole.















Part F. [5/50 points] (grammars)

With donut consumption increasing, your innovation is making nutritionists worldwide very anxious. To quell their concerns (and ensure future business) you offer the following suggestion for a well-balanced donut:

A donut is well-balanced if it produces a sequence of measurements according to the following grammar (with start symbol S): 

  S  ->  Z D Z

  D  ->  1 D 1
  
  D  ->  0 Z

  Z  ->  0 Z  | λ
where the lambda ( λ ) indicates the empty string.

Give an example of a measurement sequence from a well-balanced donut, and provide its parse tree according to the above grammar. Are well-balanced donuts a superset or subset of premium donuts? In what sense are they well-balanced?



















Part G. [10/50 points] (prolog and parsing)

Wanting to take advantage of the popularity of this new variety of donut, Hostess and Entenmann's (the donut companies from part E) try to write a regular expression to match the measurement sequences of well-balanced donuts. After a couple of days of unsuccessful effort, however, the companies suspect that they might need stronger computational tools to solve their problem. Hoping to send its rivals into an endless abyss of instantiation errors, Krispy Kreme suggests that they try using prolog to solve their problem.

Despite Krispy Kreme's intentions, prolog turns out to be a very capable tool for determining whether or not a donut is well-balanced... .

Using any of prolog's built-in predicates or those you wrote in the assignments (reverse, append, etc.), write a prolog predicate wb( L ) that is true (says yes) when L is a measurement sequence belonging to a well-balanced donut. wb( L ) should be false (i.e., should say no) otherwise. You may want to write some additional predicates to help you define wb.

Assume that L is the usual comma-separated list of 0's and 1's. (Recall that prolog handles lists in the same way rex does.)