Problem 1 a(i): 7 (ii): 6 b: Yes, it can be drawn in a plane as seven separate asterisks (separated by appropriate spaces), each with a day-node at the center and radial arms to appropriate number-nodes. Problem 2: 0 0 > (( {0} )) -----> (( {0,2} )) -----> (( {0,1,2,3} )) <-----. \ \ \______/ 0,1 ">" marks the start-state. Doubled parentheses mark accepting states. Problem 3: a: 0 | | V 2 |\ | \ V V 1 3 There's a backward arc from 0 to itself, a backward arc from 3 to itself, a cross-arc from 3 to 1, a backward arc from 1 to 2, and a backward arc from 1 to 0. b: 0 | | V 2 | | V 3 | | V 1 There's a backward arc from 0 to itself, a forward arc from 2 to 1, a backward arc from 3 to itself, a backward arc from 1 to 2, and a backward arc from 1 to 0. Problem 4: a(i): Yes (ii): Yes b(i): 4 (ii): {a,b,g,h} c(i): 4 (ii): {c,d,e,f} d(i): 4 (ii): At most one of the square's edges can be dropped (else disconnection would occur), and no radial edge can be dropped (similarly); and dropping a single edge of the square does yield a spanning tree; so there are precisely 4 legitimate possibilities. Problem 5: a) type recType = {node: int, adj: int list}; b) case x of "" => false | _ => true Common errors were confusing "" with nil or getting the order of patterns wrong. Remember ML tests from the top until it finds a match. c) The response to !num is val it = 1 : int and the response to num is val it = ref 1 : int ref Problem 6: a) XabbX (remember, X stands for (a|b)* ) b) XaXbXbX c) aXbXbX | baXbX | bbXaX (among many other possibilities) Problem 7: Since w is in L(R|S), it is in L(R) or L(S). Case 1: w is in L(R). Then w is in L(R*), since the latter includes L(R). Also, epsilon is in L(S*), because L(S*) includes L(epsilon). Thus, w concatenated with epsilon (which is just w) is in L(R*S*) by the definition of the language of a concatenation. Case 2: w is in L(S). Similarly infer that epsilon is in L(R*) and w is in L(R*), so w is in L(R*S*).