Problem 1 a: --> "-" --> 3 | 5 | 7 --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 b: --> 7 2 Problem 2 a: ( a | b )* c b: a b a* b a* c: b ( a a b )* Problem 3: a) Always use production (1). b) Use production (2) if the first character is 0, use production (3) if the first character is 1, otherwise fail. c) fun s(l) = a(a(l)); d) fun a(0::xs) = a(xs) | a(1::xs) = xs | a(_) = raise Fail Problem 4: rs 00 01 11 10 --------------- 00 | 0 | 0 | 1 | 0 | |---------------| 01 | 0 | 0 | 1 | 1 | pq |---------------| 11 | 1 | 1 | 1 | 1 | |---------------| 10 | 0 | 1 | 1 | 1 | --------------- Problem 5: a) val append01 = cat [0,1]; b) val append23 = cat [2,3]; c) val append0123 = append23 o append01; Problem 6: a, b): Here are the prime implicants: ___ ___ __ _ _ _ _ pr prs pqr qrs pqs pqs qrs c) There are several sets of 4 that are minimal and also some with 5 that are minimal in the sense that no one can be thrown away. Here is one set: ___ __ _ pr prs qrs qrs Problem 7: Definitely the hardest on the exam. Many people brute-forced it, in effect drawing a Karnaugh map and finding the prime implicants. That is OK, but it is more work than Problem 4 for less credit. The people who did this correctly got rp+rq+pqs for (a) and __ __ ___ rp+rq+pqs for (b). Another approach is to note what a node cover says about each edge: at least one end is in the set. Thus, the edge {p,q} "says" (p+q) must be true. Similarly, each edge says the OR of its endpoints, so a quick solution to (a) is (p+q)(p+r)(q+r)(r+s). Likewise, an independent set causes each edge to say at most one end is _ _ in the set, so edge {p,q} says (p+q). A solution to (b) is thus _ _ _ _ _ _ _ _ (p+q)(p+r)(q+r)(r+s).