Well, as the semester comes to a close, the last day of classes completed, it is time to reflect on how this course has helped me change.
I had high expectations as to where I would be right now. I expected my theoretical/mathematical background to evolve exponentially, as the material would not only take me further, but bring back where I left off in CSC165 three years ago before I left for the life sciences. I feel that while I did evolve, realistically I realized I had set the bar too high. Let me point out that this has nothing to do with the course material or administration, it is merely a personal thing.
I struggled through aspects from the course, mainly induction. I found it difficult to visualize mathematical relationships and concepts in my head. However, when I sat down and thought it through for a while on paper, I was able to work it out. While this strategy worked on Assignments, during tests I took a critical hit.
My favourite topic of the course? FSAs. From what I have described above, it's obvious why. Drawing out machines using good 'ol fashioned paper and pencil allowed me to visualize the mechanics behind what our goal was. Not only that, but they rarely required proof, haha.
These FSAs helped me discover that I'm a visual learner, and need to have a paper and pen ready to map out what I'm working towards. This led me to the discovery that I'm disorganized, and that drawing things out on paper aided my focus. You may have noticed that my first Slog entires were a disorganized mess. I hope I have improved since then. I guess you can say that In addition to gaining knowledge of the course material, It was a victory on the personal front too, but not what I expected.
I have begun to study for the final, taking plenty of paper to write out my thoughts first before directly diving into a proof.
The worked problem examples given in the Slog handout are indeed helpful, and while I did not use them on this Slog, rest assured I am putting them to good use, haha.
It has been a long day, and an even longer semester. I mentioned that I was struggling with the material, but I sat down to review and I understand now what's going on. The topics in the course have got me excited for the continuation course - CSC263. I feel that I just need more practice to build up my speed and to help me recognize patterns easier.
Thank you for an amazing experience.
Friday, December 5, 2008
A3
Since it's the last day for the Slog, I assume it's ok to now post the entry I wrote a couple of weeks ago about A3. Also, I figure no one will find this anyways. The email said we couldn't post it on the bulletin board :p
I wanted to work through Question 3, something I had my doubts about.
The question was to prove that for any Regular Expression that does not include a kleene star (*), denotes a finite language. I felt that while the question seemed obvious, it was difficult to prove.
After spending a long time thinking of a decent way to prove it (procrastinating by working through problem 3), I had an idea. I won't give the direct proof, just the outline of what I did.
I devised a plan to literally break it down into smaller (finite) elements.
I thought that if a Regular Expression R is defined by structural induction, then there must be a way to break do break R down into smaller Regular Expressions such that:
R = (R_1)(R_2)...(R_n) for all n in the natural numbers n.
Now, if R did not include a kleene star, then obviously the smaller (R_n)s do not either.
Thus, since we are using our alphabet of /Sigma = {0,1}, each of those regular expressions (R_n) must be either: the empty expression, /epsilon, 0, 1, or (1 + 0).
Each of these regular expressions themselves denote a finite language with a length <= 1. Thus, R altogether must be of length <= n. This means that there is a finite length we can assign to strings denoted by the language R.
Thus, with our finite language /Sigma = {0, 1}, our worst case string for a regular expression of length n is that the string is of length n. Since we have two characters in our alphabet, the number of combinations of those two characters is 2^n.
Depending on the length of R, we can see a finite number of strings that R can denote, thus L(R) denotes a finite language.
The only way for R to denote an infinite language is for one of those smaller RegExes (R_n) to contain.. on let's say.. a kleene star.
I wanted to work through Question 3, something I had my doubts about.
The question was to prove that for any Regular Expression that does not include a kleene star (*), denotes a finite language. I felt that while the question seemed obvious, it was difficult to prove.
After spending a long time thinking of a decent way to prove it (procrastinating by working through problem 3), I had an idea. I won't give the direct proof, just the outline of what I did.
I devised a plan to literally break it down into smaller (finite) elements.
I thought that if a Regular Expression R is defined by structural induction, then there must be a way to break do break R down into smaller Regular Expressions such that:
R = (R_1)(R_2)...(R_n) for all n in the natural numbers n.
Now, if R did not include a kleene star, then obviously the smaller (R_n)s do not either.
Thus, since we are using our alphabet of /Sigma = {0,1}, each of those regular expressions (R_n) must be either: the empty expression, /epsilon, 0, 1, or (1 + 0).
Each of these regular expressions themselves denote a finite language with a length <= 1. Thus, R altogether must be of length <= n. This means that there is a finite length we can assign to strings denoted by the language R.
Thus, with our finite language /Sigma = {0, 1}, our worst case string for a regular expression of length n is that the string is of length n. Since we have two characters in our alphabet, the number of combinations of those two characters is 2^n.
Depending on the length of R, we can see a finite number of strings that R can denote, thus L(R) denotes a finite language.
The only way for R to denote an infinite language is for one of those smaller RegExes (R_n) to contain.. on let's say.. a kleene star.
Subscribe to:
Comments (Atom)