Week Nine

Monday,
---------- Nov. 3, 2008
Today, we started chapter 7 which discusses strings and regular expressions. We began by defining alphabets, strings, and languages and the various operations that can be applied to them. Everything sounds okay except for the Kleene star. At first I thought it is something like the Cartesian product of the language itself, but it turned out to be infinite. I guess I can think of it as "infinite Cartesian products of the language itself"??


Wednesday,
---------- Nov. 5, 2008
Today's lecture was about regular expressions. This term is familiar from CSC207. We have three main operations; "or" (I do not know why is it + rather than |), "concatenation", and again, "Kleene star". Good thing to keep in mind when doing proofs related to RE, is to use the inductive definition itself. Consider three base cases, \phi, \epsilon, and (a) for some a \in \Segma. Then use structural induction in the induction step.
Finally, we discussed how to prove that two languages are equivalent. It is a two-way proof. Prove the first is a subset of the second, then prove the second is a subset of the first, and conclude that they are equivalent.


Friday,
-------- Nov. 7, 2005
We had term test 2 today. The test was fair, I honestly expected something harder. There is one thing is bugging me though. In the last question, I did not need to prove a loop invariant; I just showed that there is a decreasing non-empty sequence of natural numbers. I hope this is enough.