DFSA

In some degree, the most challenging question in assignment 3 may be the last one.
I once got stuck on combing the two machines representing binary string with odd length and multiple of five respectively. I wasn't sure what were the exact steps using cartesian product. So i considered all the combinations of the cases of the third machine i want to construct.
That is exactly the result of cartesian product. Excluding the initial state, there are 5*2 = 10 states
for x = n mod 5 with odd/even length. These are the state invariants. Then We can see directly from some binary numbers and derive the transitions. Then the desired machine is fulfilled.
The proof of a DFA is straightforward. For me it is kind of a process of verifying each state go to the correct place via a path or an edge. Graphically, each state is a node with inputs and outputs.
Thus the transitions explain the correctness of traversals in a machine.

review of Week 10

The annoying assignments, exercises, quizzes and term tests seem to be paused except for CSC236. This weekend i have to engage into the second last assignment with my partner. I also have a somehow big project of csc207 to worry about. Insipte of the workload of a computer science student, i now write for my 6%~11% of the final mark.
These two week we saw pretty much things about finite state automata and regular expressions. Regular expression is a descriptive way to express the language. We can design our own language with different alphabet using regular expressions. Through the example in the lecture, such as an alphabet of binary numbers containing even or odd zeros, i learned a logical procedure to analyze the syntax between various languages. The interesting part for me is the algebra on regexes. Without changing the language, one can apply some principles such as: commutativity, distributivity to the regular expressions. This simplifying process allows more variations on a language and it provides some interesting design patterns of a language.
Another thing is the DFA, or DFSA. The first time i saw it was in CSC148 when we were doing the graph algorithm. It seems there is quite a few connection from the DFA to graph algorithm. Machines of DFA accept their unique pattern of strings. We can easily find out whether a string is valid to the machine by traversing between the states. The hard part is how we construct a desired machine for a particular collection of strings. By observing the pattern of some strings, we need to derive some crucial parts of the machine like the state invariants and the transition functions. A graph is usually helpful to verify the state the next character heads is correct, which is to say, we need to carefully set our initial state, final state, states between and all the edges. Such things is really thoughtful.

After Test 2..

Since there is always a lot of people there in the day section, i wrote the night section test.
I don't know how big the difference between the day section and night section test. They may follow the same patter pretty much. I didn't work out satisfying answers on the test.
About the palindrome, i remembered well that i did the same thing in CSC108 lab. But one thing
to regret is that i forgot the prove structure. I tried using complete induction but i didn't organize the frame well.
Related to the last question in the test, i really got a mess in my mind during the test.
I got frustrated when i could not figure out right away the main purpose of the function downward(n). Things happened and i got all blank in my brain. When i got calm down and refreshed my mind, i tried out some typical examples. Unfortunatley, i didn't realize that the loop invairant was sth like the floor of lgn until hours after the test. Anyway i cannot say i fail the test, at least i failed getting an insight on the subtle things.