November, Week 11

Another week has passed... And it is also almost the second last week before the exams. Which are pretty much the end of this semester. Which means that the end of this whole school year is also almost over, only one more semester to go. And from there graduation is not so far away. In terms of CSC236, this week was about different applications and techniques of FSA's. I found the cartesian product of two DFSA technique quite interesting. For some reason I thought that,

despite the fact that there always exists a union of two regular expressions (and therefore two DFSA's), the way to find this union is more or less trivial. And summing up what we have learned this week, it turns out that there exists an actual technique. By building DFSA's of both regexes, then using cartesian product to get a union DFSA, and finally decomposing it to get the final regex, you can pretty much find any union. And this means it is easy to find any possible regex. Just divide it into smaller parts and use the technique to find intersections. Very nice.

November, Week 10

The main theme of this week was the finite-state automatas and deterministic finite-state automatas (I wrote full names on purpose, so that this slog entry appears bigger. This remark is written for the same reason). Finite state machines are a very interesting topic, and I actually find it pretty amazing that a machine that performs a single transition based on a finite state it is in, and the data it sees, can do some pretty amazing stuff (like determining if a string is a multiple of 3 in base 2 or not). Consider a Turing machine. Although it is not exactly what we studied in class, it has many similarities with a DFSA. A 5-tuple Turing has instructions in the form of (q, ss, sp, dir, q'), where q and q' are states, ss and sp are symbols (e.g. '1' or '0'), and dir is direction to move the tape (left or right). This 5-tuple basically translates as


if (current state == q)
{
if (see symbol ss)
{
erase ss and print symbol sp in its place;
move tape in direction dir;
current state = q';
}
}

As simple as this machine is, it is actually able to simulate the logic of any computer algorithm.
First I couldn't believe it, but it turns out that it is actually true. I started researching and I wanted to find an RSA encryption algorithm written on a Turing machine (most likely a 1000+ page text file of state invariants), but I was not able to find one.

November, Week 9

This week we have been introduced to the concept of formal languages and regular expressions. Although I am quite familiar with regular expressions, as I have used them a lot with various programming languages, my knowledge was not relevant, because csc236 tends to look at everything from a different perspective, a more in-depth, "theoretical" approach. For example, I never thought of multiplying or adding, or dividing regular expressions when I used them :) I even found out that there is such thing as "Kleene algebra". The concepts were still pretty straight-forward, so this is pretty much everything I can force myself to write.

October/November, Week 8

This week we continued on the topic of program correctness, but the emphasis was on loops. I found the concepts straight-forward, except for the double loop that Danny Heaps proved on Friday. The proof turned out to be rather long, 4 (!) full slides.