The End is here!

The entire semester has been a very trying one, yet very interesting and fascinating at the same time. Learning about finite state automata, understanding strings as mathematical sets, program correctness, context-free grammar all truly tested my problem solving skills.

Recently, I solved a problem that asked us to Prove that any regular expression that doesn't include a Kleene star denotes a finite language.

Initially, I attempted to solve this problem using induction. This turned out to be an extremely complex approach, instead, we were directed to look at the definition of what makes a language and its regular expression properties.

By studying the notes, we see that any language that is Kleene star, it also has the properties of (R+S) and (RS). So if we can prove the latter of the two, we have satisfied our problem.

Basis: 0, epsilon, and a (for each a in sigma) are in the RE of sigma

Induction step: If R and S are in RE of sigma (ie: R and S are regular
expressions of sigma), then so are (R+S), (RS) and R*.

We know by definition that the Kleene star for any language is the set of all
possible concatenations of 0 or more strings in L. Hence, since (R+S) and (RS)
both are also valid regular expressions of sigma, by proving that those
are the regular expressions of finite languages, our proof is complete.

To prove this, we examine the definitions of what makes a regular
expression for a language L.

Let P(n) represent the regular expressions (R+S) and (RS) for the language L
where L is a finite language.

Let the language be denoted by a regular expression R be called L(R).

Base case: L(0) = 0, L(epsilon)={epsilon}, L(a) = {a}. All of these regular
expressions denote a finite language. Since L(0) only contains 0 strings, which
is finite. L(epsilon) contains the finite string epsilon, and L(a) contains
the finite string a.

Inductive hypothesis: if L(R) and L(S) have been defined, then L(R+S) is finite
and L(RS) is also finite.

Inductive step: We have to prove two cases: that L(R+S) is finite and that L(RS)
is finite.

By definition, the property RS means that for every xy where x and y are in the
set of natural numbers, x is an element of R and y is an element of S. Secondly,
if |R| = k (for some k in the set of natural numbers) and |S| = l (for some l
in the set of natural numbers), then the upper bound for the maximum possible
concatenations of RS is kl.

Similarly, the property of R+S means that for every x that is in R and ever y
that is in S, R+S = x+y. By definition of union, R+S may consist of x, or
consist of y or neither x nor y for every x and y in the set of natural numbers.
Thus, the upper bound for |R+S| is x+y.

Since RS and R+S both have an upper bound, we have shown their maximum
combination of strings possible. Thus, we have demonstrated that L(RS) and
L(R+S) both denote finite languages since they can only contain a maximum
number of strings.

Therefore, any regular expression that does not include a Kleene star denotes
a finite language.

End of the term and courses...

So it's hardly believable that with November coming to a close, the fall semester is almost at its end. Things are getting busy again, what with our final assignments and tests coming our way, and then the dreaded finals before we're off for Christmas break. Looking back, this course seemed way more intimidating than I'd expected it to be back in September. Looking at things like studying induction (always frightened me), program correctness (had no clue how you can mathematically prove a program is correct), formal languages and context free grammar didn't exactly seem all that easy to understand. So to be really frank, it really isn't that bad. Not to mention, it's also pretty interesting stuff.

I'm glad that I'm able to understand some of the theory behind computation and programming. Formal languages gave me a new perspective on looking at language altogether - who knew you could apply set theory to language?? I never thought of that; but after having studied it, it makes perfect sense.

For the final test and problem set, hoping to do well and end the course on a good note. It's been a good experience so far, and I'd like to see it through to the end that way.

Learning New Things...

As we studied program correctness last week, I learned quite a few new things. Amongst that was the fact that you can actually mathematically verify how smart a program is. Along with checking time complexity, through program correctness one can study loop invariants, come up with closed forms of recursion - all of this is applicable to regular programming concepts like binary sort or merge sort. Who knew!

We also began learning about formal languages. Now we are comparing the structure of language, the sets of alphabet. And the neat thing is being able to tie that in to programming: (from the lecture slides)
If x and y are strings, then we can talk about:
{ The length of x, jxj. So jj = 0
{ The concatenation of the characters of x and y, xy
{ The reversal of the characters of x, (x)R, so (string)R = gnirts
{ The kth power of string x:

Who knew?? This continues to teach me new things as I'd never in a million years imagined being able to analyze recursion or iterative loops in mathematical program correctness. Now I'm even more amazed at being able to analyze a set of letters! Who'd have known the alphabet could be mathematically studied?? It is taking a simple group of letters and applying set theory just as we study it mathematically. Neat. can't wait to learn more.

Assignment 2 and Prob Set 4

We are studying program correctness - who knew that you could analyze program correctness mathematically? I already found it interesting when I learned that recursion is similar to induction! So mathematics actually is applicable in programming, not just to teach you how to think or problem solve. Program correctness is pretty neat. I remember learning about O(n) complexity and thinking, how can I use this? But only to be surprised.

The interesting thing about this is that we don't just analyze the accuracy of the code. We also look at the pre-conditions, post-conditions as well. So we study how to test the accuracy of the entire program altogether - great and useful stuff!

Fall season...

Now that the fall term is in full swing, I'm beginning to get a taste of what the rest of the term is going to be like. The workload gradually gets heavier, the concepts become tougher, and midterm season is kicking in. We had our first term test last week. Induction actually seemed to be getting less intimidating for me through the examples we studied in class, and through everything we've been learning in the problem sets and assignments. The test really put me to the test by pushing me to think and prove induction problems in a shorter time span. Although induction still remains a challenge, it is getting better for me.

We're on to studying recursive functions. Next to induction, this has to be the second most frightening topic for me. So far, understanding it has been fairly doable. We'll see how I fare on the third problem set. I know that with induction, I was able to understand it better this time around, so I can say with some confidence that hopefully recursion should also become better this time around for me.

Will update soon.

My very first Blog

It has been my first month back at school, and also my first month of studying CSC236. Most of my other courses have been spending the last two or three weeks immersing us back into school work gradually. CSC236 got us to jump into the waters right away - we've already handed in two problem sets, and our first assignment is on the way.

The course has been pretty neat so far. Normally, induction has always frightened me, but for once, with the way I'm learning it now, it actually doesn't seem as intimidating. I've been able to solve the problems (with help of course) and actually understand the concepts - yay! I'm not as scared of the course as I was when I first began the term. (But who knows, the tough stuff is yet to come...)

I've never really maintained or kept a blog before. This is my first. Let's see how it helps....hopefully this will become a diary of sorts to help me throughout the course and better prepare me to study in the future.