Weeks 11-12: NFSAs/Pumping Lemma + Non-regular Language

Again, I'm writing a blog for 2 weeks, which is pretty bad as of the blog requirement. I will definitely write one for the last week of class! Looking back to week 11, we dealt with a lot of problems of NFSA and the new concept of the Cartesian product that was used in dealing with one of the problems for A3. There was indeed some confusion and difficulty when combining the two machines, binary string of odd length and multiples of 5 into one huge machine. If I remember correctly, I had about 16-18 states to list out. But the lecture material really did help in clearing up how to write up the Cartesian product of the delta function, accepting and starting states. Danny also went through a few examples showing how there is a regular expression for every FSA. However, I run into problems of choosing which state to remove first when trying to express the FSA to a regular expression.

We started off week 12 looking into the pumping lemma and proving it. Unforunately, the projector burned out again during lecture and everything was done on board. We were also introduced to grammars that contained productions and states denoting a language. Perhaps more examples can be found in the textbook. If possible, it would be great to see lectures posted from the evening class for revision of the test on Friday.

Week 9-10: Formal Languages and DFSA

It's been 2 weeks since I've writing a blog.. I know we should be writing weekly, but I tend to easily forget with all the assignments in MAT, CSC207 and all. Well, test 2 was handed back in Week 9 and it wasn't as good as I thought it'd be. I lost some marks on Q2 and I really didn't have time to finish up Q3. By the time I thought of an approach, the time was up. I guess I'll be having this test to take the least weight of all assignments and test. More intense studying will be needed for test 3! Formal languages and regular expressions were introduced and both of them are brand new material. I still have to get used to remembering all the possible operations of *, +, ? and this is definitely a problem when it comes to doing A3.

DFSA was the core material learned in week 10 and the drawings of the machine with arrows and circles doesn't seem to complicated at the moment. However, when it comes to submitting assignments in text file without the drawing, that will definitely be an issue for me. If only we could submit the picture somehow, then life would be so much better. We also looked into the intersection of languages, which is quite hard to express using regular expressons. I wonder how the DFSA questions will be on the upcoming test 3.

Week 7-8: Program Correctness and Termination

The use of iterative and recursive functions are widely used, but rarely do we prove that a program is correct and produces the correct output for every passable input by some sound argument. In week 7, we looked into the proofs of how preconditions and executions implies the postconditions. When we assume that a program is correct, some assumptions are made and we believe they must be true for every computation at the end of each iteration. This is known as the loop invariant and by stating this, it certainly helps me in understanding the iterative algorithms as a coder and reader. It's important to establish the loop invariant, as well as maintaining it before we exit the loop. In A2, it was definitely some challenege to prove that m = int(mat.sqrt(b*e)) actually worked for binary search, compared to m as the midpoint of the left and right. If m was correct, then indeed everything else would flow. Otherwise, it would be necessary to disprove by a counter example for its program correctness.

The above elements only checks for partial correctness of a program. To further develop a solution, we must also show that the loop terminates at a certain point of the loop. This is known as termination, which we looked at in week 8. I have a feeling it's going to be something big on the upcoming test and I should review more on the material of termination and correctness in the textbook and other examples online.