Week 10 - Regexes, FSAs

DFSA (Deterministic Finite State Automata) is a machine with transition functions, it shows regular expressions for things like L1 AND L2. Its name scared me for a second, but designing a DFSA was not as hard as it seemed. For the questions we discussed in lecture, the state invariant was pretty easy to figure out, the transition function that moves the machine from the present state to the next state was quiet straight forward, then the sketch of the transition to different states followed with logic. I think I did something similar to this before for circuits.

PROBLEM SET #5

This is a very easy problem set, the question is almost identical to the example given in lecture. But it's good that it got me looking over the slides again to review what I've learned.

Week 9 - Formal Languages

A language is a set of strings, and a string is a finite sequence of symbols. Therefore, we can use set operation and string concatenation on languages. The complement, unions and intersections of two languages, L1 and L2, are all the same as set operations, so that is not too hard to follow. A new term that is introduced is the "Kleene Star", which I've never heard of before. But the concept behind isn't hard, it is just "all possible concatenations of 0 or more strings". Exponentiation and reverse are a bit more complicated, but they are not that hard to master either. The most difficult concept of the lecture came when we were to prove a regular expression. I followed the example in lecture closely, understood most of it, but I still don't get how it came up the conclusion. I will read the lecture slide and course notes over the weekend and try to figure it out by myself.


TERM TEST #2

I spent almost one whole night studying for this term test, but I didn't expect week 8's material to be included in it so I only studied up to week 7. The first two questions were all pretty straight forward, basically after reading it, I had a clue as to how to proceed. But for the last question on proving termination, I had no idea at all! Next time, I better not gamble on it. Should've studied everything up to the lecture before the test just to be on the safe side... =(

Week 8 - Iterative Correctness

This week, we have moved our attention from recursion to iteration (looping), which is also an implementation of repetition. But the difference is, for iteration, we are also checking that the loop eventually terminates with its work done. Termination means that there is some decreasing sequence of natural numbers, , where i is the loop index. Other than this, it contains pretty much nothing new. The proof procedure is still the same: using Simple Induction. I found no problems with this week's materials.

To continue with what Danny left on the Wednesday slides for the counter example:
Show that 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 1: If bi != 0, then from line 5: b(i+1) = bi - 1 and a(i+1) = ai since a it is not modified anywhere. Therefore, 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 2: If b = 0, so a != 0, then from line 8: a(i+1) = ai - 1, and from line 7: b(i+1) = 6. Therefore, 7a(i+1) + b(i+1) = 7(ai - 1) + 6 = 7ai - 7 + 6 = 7ai - 1 = 7ai + bi -1 (since bi = 0).


ASSIGNMENT #2

I wouldn't consider this assignment to be very hard, but due to the amount of workload from other courses (midterms, projects, etc.), I was not able to start on this assignment until one day before the due date. With help from the TAs, I solved all the questions with no problem. However, I couldn't finish typing out the final copy before 10pm. I left out question #4 unfinished, and this is really going to kill my mark. I assume at least 20% will be deducted... Now, I regret so much on how I wasted my time earlier. Even half an hour more would be enough to save this 20%. =(

Week 7 - Program Correctness

Recursion can get me very confused at times, it usually takes me long to figure out how it works. The theory of it isn't hard, it's just when it's applied in a function, I sometimes can't get myself out. I know this means that I need more practice on it. When writing a recursive function, I often can't see how the problem can be broken down into smaller problems to use for base cases, but I'm much better with its proofs since it's basically 'proving by Simple Induction'. Now, I feel like this course is going to help me alot when I write programs... it's not just about proofs afterall.


PROBLEM SET #4

I didn't have any problems doing this week's problem set at all. This problem was an easy one. All it needed was using logics and breaking the problem into smaller problems so that it can be proved using induction.