Problem-Solving Exercise, Part 1.

I have decided to draw the 16-state DFSA from A3, Q1, instead of the difference engine I said I was going to take a look at. I don't know if I'll have time for the difference engine, and I had already completed most of this before I realized that I could do this for the problem-solving exercise. I'll scan some of the process work I did in pencil, but I've redrawn it on the computer.

1. UNDERSTANDING THE PROBLEM
   • What is the unknown? What are the data? What is the condition? 
   • I know that I have to come up with a 16-state DFSA that describes the language of binary strings whose fourth-last bit is 0. I do not know, at first, how the states will be connected, especially once they branch out after an accepting state has been reached. Each state has to have an edge labelled 0 and an edge labelled 1 coming from it, because every binary string can be made bigger by a 1 or a 0 added, and this DFSA has to handle all possible binary strings.
   • Is it possible to satisfy the condition? Is the condition sufficient to determine the unknown? Or is it insufficient? Or redundant? Or contradictory? 
   • Yes, I believe intuitively that this is possible, especially since we need to prove in assignment three that no DFSA with less than 16 states can handle this language. I know that I can only have 16 states, so it is just a question of how to connect them.
   • Draw a figure. Introduce suitable notation. 
   • Figures will be provided as they evolve, in each entry.
   • Separate the various parts of the condition. Can you write them down? 
   •  The condition is the entire DFSA.
2. DEVISING A PLAN
   • Second. Find the connection between the data and the unknown. You may be obliged to consider auxiliary problems if an immediate connection cannot be found. You should obtain eventually a plan of the solution.
   • Have you seen it before? Or have you seen the same problem in a slightly different form? 
   • We have handled many binary-string DFSAs in class and tutorial. The problem is loosely related.
   • Do you know a related problem? Do you know a theorem that could be useful? 
   • All of our binary string problems have been related, in a way, because many of them deal with binary strings that may be repeatedly accepted as they grow. I cannot think of any theorems I would apply now. 
   • Look at the unknown! And try to think of a familiar problem having the same or a similar unknown. 
   • I don't know that we have ever been given a problem where we need to construct a DFSA with a precise number of states.
   • Could you restate the problem? Could you restate it still differently? Go back to definitions. 
   • I feel it's pretty clear.
   • If you cannot solve the proposed problem try to solve first some related problem. Could you imagine a more accessible related problem? A more general problem? A more special problem? An analogous problem? Could you solve a part of the problem? Keep only a part of the condition, drop the other part; how far is the unknown then determined, how can it vary? Could you derive something useful from the data? Could you think of other data appropriate to determine the unknown? Could you change the unknown or data, or both if necessary, so that the new unknown and the new data are nearer to each other? 
   • At first I had trouble connecting the accepting states to further elaborations, so I just drew the DFSA below, which is incomplete. I did not know at first how to handle any strings longer than length 4, who have already had a previous section of themselves in an accepting state.
   • Did you use all the data? Did you use the whole condition? Have you taken into account all essential notions involved in the problem? 
   • In the figure below, no. It only works for strings who have not yet gone through an accepting state.

This was my first attempt at the DFSA. It has 17 states because I wasn't sure yet how I would handle a string where the fourth-last bit wasn't 0, so I did a separate state for that, and for an empty string, which I later realized could be combined (states q0 and q16). The DFSA in this image isn't complete because at first I wasn't sure how I would connect the accepting states if they had bits added, for example, this DFSA handles every binary string of length 4 whose first digit is a 0, but it can't handle any longer strings that are build from previously accepted strings, like 00001 - I didn't know at first where the arrows from the accepting states would be going.