Homework Due Tuesday, January 24

0.7, 0.9 (for this problem, use A={1,2,3} and B={4,5,6}), 0.10, 0.11, 0.12
Consider the relation S defined as follows. (1,1) is in S. If (a,b) is in S, then so is (a+1,b+2a+1). S is the graph of a well-known function. Determine what this function is, and then show (using induction) that your solution is correct.
Do not bother to hand in 0.13 and 0.14, but do try to solve them before you read the solutions. (Also, make sure that you understand the other excercises in this chapter, even though you are not to hand them in.)
1.4.e, 1.6(c,g,i), 1.7.b, 1.9.a,

Homework Due Tuesday, January 31

1.10.c, 1.14.b, 1.15, 1.16, 1.17, 1.18(c,g,i), 1.21, 1.31, 1.34, 1.51

Homework Due Tuesday, February 7

1.29.b, 1.32 [Give a minimal DFA for the reversal of B], 1.35, 1.40.b, 1.46(a,c,d) [Note: some of these may actually be regular.], 1.49, 2.4.e, 2.6(b,d), 2.9, 2.14, 2.35

Homework Due Tuesday, February 14

2.5.e, 2.10, 2.11, 2.20, 2.23, 2.25, 2.28.a (why is your grammar unambiguous?),
Consider the following grammar:
S -> AB | CB | a | b
B -> AS | SC
A -> a
C -> c
Determine if the following strings are generated by the grammar: caaac, caaab
For Extra Credit: 2.24 (this is challenging)