Regular expressions, and their equivalence to DFSAs

The recent lecture material on regular expressions has been pretty interesting, and I found it cool that every regular expression can, in principle, be represented by a DFSA (it makes sense, when you think about it).

The most recent lecture about "multiplying" DFSAs was also cool; by running many DFSAs in parallel you can find the intersection of strings accepted by each one (i.e., the set of strings accepted by all of them). This also makes intuitive sense, but makes it a lot easier to create complicated DSFAs by making each one act as a "filter" for a certain condition (as opposed to trying to make one from scratch that satisfies many conditions).

I've looked at the Assignment 3 questions, but due to a large Machine Learning project I haven't made much headway on it yet. I don't really understand loop invariants yet, so I'll need to read about them. The course notes have been a pretty useful resource the past few weeks, so I should be able to learn what I need from them.

I've noticed that I still haven't posted a specific "mathematical" problem on this blog yet, so I'll need to do that soon! I've found the material from the past 2 weeks or so to be the most interesting in the course so far, so it will probably be related to DSFAs and/or regular expressions.

Post-Test 2, and the beginning of finite state machines

Well, last week's test went decently. The one thing that kind of tripped me up, though, was the last question. After all we've done since the first test (e.g., proving that a function is non-decreasing, unwinding recurrence relations, etc.), I was definitely not expecting to rewrite a program function. It was either way too obvious and I overthought it (just square the first recursive call!), or I completely missed something subtle. We'll see.

Anyways, the topic of this week's lecture and tutorial seems pretty interesting. Back in high school, I had a final project for my geometry and discrete math class, and I decided to do it on cellular automata. I didn't go too deeply into the theory at that time (it was more a survey of the field), but even then I was impressed by some of the potential applications of it. I especially liked Conway's "Game of Life" (I even tried to write a simulator in Turing).

It looks as if the FSMs we will be working with (at least at first) take only binary strings as their inputs and accept or reject them. It will be interesting to see how the rules for designing and proving the correctness of FSMs like this can be applied to more complicated ones with more interesting inputs!

More recurrence relations, and bounds on complexity

In finishing up the second assignment, recurrence relations (particularly, the Fibonacci sequence) came up once again. Once I noticed the pattern, it was obvious to see that it was directly related to the Fibonacci sequence (one digit ahead of it), but I unwound it and recombined it to get some practice.

It's interesting how every recurrence relation which somehow involves the summing of the two previous numbers in the sequence has a closed form related to the golden ratio. In the Fibonacci case, the golden ratio satisfies the equations

so the powers of the golden ratio satisfy the Fibonacci recurrence. It's cool to see how it works!

In other news, I've been having some difficulty keeping up with all the new material that gets covered in tutorials. My tutorial section has been a little bit unhelpful in clarifying my difficulties. I plan to do whatever reading I have time to fit in before tutorials (although time is still at a premium).