Interesting assignment 3. I am starting early because I also have a CSC209 assignment coming up, and those frequently take a substantial amount of time, not to mention I have a midterm on the Wednesday of the week this assignment is due. Good to start early. Question number one has me stumped. I am probably going to attend office hours tomorrow. Ask a few questions. I have come up with an approach, which I think is headed in the right direction. Question one asks: 

Let L = {x is in {0, 1}* | fourth-last symbol in x is 0}. Prove that any DFSA that accepts L has at least 16 states.

We know if DFSA M, accepts L, then for any string s in L, the first state that s drives M to is necessarily in Q. That is the state that s[0] drives M to is in Q.  Also  every state that s[i] , i=1,2,......,n drives M to is also necessarily in Q, and will transition from state to state according to transition function *Delta*. Finally we know that if M accepts string s then the last character in S causes the machine to half at an accepting state.

Im not quite sure where to go with this. The hint helps somewhat in that by showing that two binary strings of length 4 drive the DFSA to the same state, it implies that the two binary strings are the same and thus further implying that each binary string of length 4 drives the DFSA to a unique state. But I am having difficulties trying to formalize this in a proof.

I am definitely attending office hours tomorrow!