Week11: Regular expressions Proof and NFSAs

The week we first studied regular expressions, it looks like an extension of formal languages. Again, it's not hard, just treat them as special sets and do some sets operations. What I found interesting and new is  the process of proving a regular expression. I didn't expect it to be a mutual proof (we need to prove both L is the subset of L(R), and L(R) is a subset of L); I had thought that we only need to prove L(R) is a subset of L. Then I realized that I was wrong, simply proving one way doen't mean L is equal to L(R). But the process seems to be a little bit tricky and made me feel that it's just playing with English in some parts.

Then we started to draw some NFSAs. But by now, I still don't know what is the point of drawing NFSAs, since they can't tell anything meaningful to me. But the professor said there was some magic between DFSAs and NFSAs, but I didn't really catch what the magic is. :(    It seems that we'll discuss more on this magic next week.

Here are my lecture notes:

Week 10: Formal Languages and FSAs

This week, we finally finished dealing with all those abstract concepts and starts to do something easier to understand to me -- the formal languages and FSAs. For the part of formal languages, I regard them as special sets. All we need to do is just some operations on sets. Since I did a lot of sets operations and analysis last term in my previous school, this part is just the second easiest part to me in this course (the easiest part is the early part about simple and complete inductions). Then The DFSAs are very similar to what we are leaning about transition matrix in STA247. It's just a process of drawing the transition matrix into pictures.

As a result of the long weekend, the pace of the day section and the night section switches. Thus we have to do our quizzes on new materials as soon as we finish our lectures since this week. The feeling is not good, we have to really concentrate on the lecture so that we can make it in the quiz. There's no time to review before quiz! (Fortunately, for this week's quiz, we just need to draw a DFSA, which is not hard.)

Here are my lecture and tutorial notes:

Week9: Partial Correctness & Term test 2

As expected, we discussed more on correctness this week. This time, the goal and the point of proving correctness are more clear to me after I studied the past term test 2, and there was a problem asking you to prove that a program terminates and the postconditions will be met (Though later I found out that it is a topic that we hadn't covered before this thursday). It makes sense that we should use some method and find some loop invariants to prove our program will meet the postcondition and terminate. It helps us to make sure that our program is correct and will terminate.

The part I didn't quite understand during the lecture is the process of deriving conditions from pictures. Because I was absent minded for a while, and when my mind came back, I couldn't figure out how the pictures were derived, namely I didn't know what the problem is! Then I asked my friend after lecture and reviewed the slides (I didn't find corresponding part in the textbook), I thin it's just another example of proving an iterative program, but expressing with some pictures to help understand.

We had out term test 2 this week. I had been worrying about writing Python code in the exam (because I didn't learn Python before), but it turned out that the test was easier than I had expected and didn't involve programming.

The lecture note for this week are as follows:

Week 8: (Precondition + Termination) => Postcondition

I had a strange feeling after finishing this week's lecture: I did followed up with the pace of the lecture and understand what the profesor was proving, but when I think back of the lecture, I can't speak out what I learned. It's like that we first use our common sense to find some preconditions of a code, then we figure out what the code is doing and that would be our postcondition. Then the process of proving the correctness of the program just seems like we first assume the postcondition, then we just go through the program again while applying some induction to analyze the program.
But I just don't know what is the point of doing this, it seems like that we first analyze the program and get to know what it does, then we analyze the program again but using a more complicated method.

Maybe I need a discussion with someone or wait to see if the professor will tell more next week.

This week's tutorial seems different to me. We did some practice on writing divide and conquer algorithms, as I haven't learned Python before, my code just looked like a combination of C and Python :(  Fortunately, the grammer doen't matter. Then we did more practice on Time Complexity and Master Theorem, a little bit hard but was very helpful to understand the lecture materials.