IMPORTANT MESSAGE:

DO NOT copy from anyone else's homework solution, or from a solution off of the web, or from solutions from a previous class. IF you receive help from some source, it is honest (and safe) to give attribution to the source and describe the extent of the help. For example, if you do copy an answer off of the web, then write, "This answer is copied from web site X with URL Y." You will not get credit for coming up with the answer, but at least you will not be punished for plagiarism. As another example, if you discuss a problem with a classmate, but do not copy off of their paper, state, "A and I discussed this problem - A came up with this idea and I worked out the details." Then you will receive credit for the problem and have honored your friend and yourself by giving credit where credit is due.

Homeworks

All homeworks are from Sipser.

HW1: 1.{1,2,4aghi,5c,8b,10,12b,14a,16a} due 9/2
HW2: 1.{13acfin,17c,18,20,22,23ac,24,26,29,31,33} due 9/15 (Changed!)
HW3: 2.{2,3,4bdeg,6ad,9,10,11,17,20} due 9/21
HW4: 2.{18bd,22,27} due 9/23
HW5: 3.{1,3,4,5,7,14,15,18,19} due 10/26
HW6: 4.{1,3,4,7,9,10,13,16,18} due 11/2
HW7: 5.{1,2,3,4,7,9,10,13,17,18,20,22} due 11/9
HW8: 7.{4,5,6,10,23,26,27} due 12/2
HW9: 8.{2,4,5,11,14,19} due 12/7

Bonus Problems

B-1: due 8/26/04. Consider alphabet S consisting of tiles with two symbols, so symbol s_i in S is s_i = [t_i, b_i]. The symbols on the tiles are in {0,1}, so S = {[0,0],[0,1],[1,0],[1,1]}. Let
- top(w) = t1 t2 ... tn and
- bottom(w) = b1 b2 ... bn
for w = [t1,b1][t2,b2] ... [tn,bn].
Now, make an FSA that recognizes w such that (bottom(w))^R = (top(w)+1)^R, where x^R = xn xn-1 ... x2 x1 for x = x1 x2 ... xn. That is, the FSA must accept strings of tiles such that if the top and bottom string are read backwards (LSB first), the bottom is the top incremented by one.
B-2: due 9/12/04. Consider L = {x in {0,1}* | x is a binary string, x = 2 modulo 3}.
a) Give a DFA for L with three states.
b) Convert that DFA into a regular expression for all binary strings equal to 2 modulo 3, using the GNFA construction technique.
B-3: due 10/28/04 Consider a deterministic TM M with a one-symbol input alphabet and a two-symbol tape alphabet (1 and blank). M has a doubly-infinite tape, initially all blanks, and it must move its head either to the left or to the right on each step. There is a single halting state with no transitions defined on it, and it does not count toward the total number of states considered for M. If M has two states, other than the halting state, what is the maximum number of moves that it can make before it must either halt or loop forever. Give an M that makes the maximum number of moves and then halts.
B-4: TBA

Send comments to nemo@cise.ufl.edu