I find current topics very interesting, and again, the way the course was structured for this material is fantastic. First we were shown that there is an equivalent NFSA to every regex. Then, we were shown that for every NFSA there is an equivalent DFSA. Then we were shown that we can construct an equivalent (I think? Havent yet seen the rigorous notes) regex from a DFSA, by "ripping" states and transitions out. So, every regex has an equivalent FSA.
I wonder how each of these different forms of representation are useful, and how they may be used in my further studis in compsci.
Tuesday, November 25, 2008
Wednesday, November 19, 2008
Formal languages, FSA
I was completely new to regular expressions. We were introduced to regex from both the theoretical perspective in csc236, and in the practical usage perspective in csc207, at the same time.
I think this concurrent introduction from both perspectives helped quicken my learning, and I got familiar with regex pretty quick. The theoretical perspective is still harder for me though. Some regex proofs seem to require multiple induction, and it can get confusing as the concepts are quite abstract.
FSAs are quite interesting, I like its graphical nature. It is very interesting that every regex has an FSA (if we allow epsilon transitions). All in all, I really like this part of the course.
A3 is due at a really bad time though. It's another crazy week..
I think this concurrent introduction from both perspectives helped quicken my learning, and I got familiar with regex pretty quick. The theoretical perspective is still harder for me though. Some regex proofs seem to require multiple induction, and it can get confusing as the concepts are quite abstract.
FSAs are quite interesting, I like its graphical nature. It is very interesting that every regex has an FSA (if we allow epsilon transitions). All in all, I really like this part of the course.
A3 is due at a really bad time though. It's another crazy week..
Friday, November 7, 2008
Killed by test, again
I wasted about 5-10 minutes unwinding, when I didn't really need to... But the main killer is the loop termination proof, which I left as "I don't know how to do". It bothers me because it seems to be quite an elementary question on the topic.
To be honest, I didn't expect the test to have much on proving iteration. Particularly on proving termination using a loop invariant.
We've seen it only for a week, the week which is the last, and also busiest, week of the busiest run this semester. I'm an early starter, but as the deadlines piled on, this past week has been very hard. I've had no weekend at all for a while. Basically I had no time to study for the test until this thursday.
We've done no PS on it, no assignment on it, all we saw so far is a couple of examples in lecture, and very lengthy examples in the course notes. In situations like this, it's hard to know whether one's understanding of the topic is correct.
So, I still don't know if I even understand this topic enough, to do a seemingly elementary question like the one on the test. By contemplating the question more, on my way back home from the test I *think* I have a correct idea of what I should prove to prove termination. If I include the time during the test thinking about the question, that's about 40 minutes of thinking, to get an idea of what I think is a correct approach.
Essentially, the question was to me an assignment question that I had to do on a test.
I think it would have helped a lot if we were given more elementary examples, with clear explanations, on this topic. The posted past test had a question, but I didn't fully understand the solution either. The topic is not easy to understand, I think it warrants more examples than the ones we were given.
Maybe now after thinking about the test question I can look at the past test solution and understand it more. Though I doubt it. Probably have to go to an office hour, and spend a week thinking about it everyday and doing some practice questions to understand it. I wish I had the time this past week for that.
To be honest, I didn't expect the test to have much on proving iteration. Particularly on proving termination using a loop invariant.
We've seen it only for a week, the week which is the last, and also busiest, week of the busiest run this semester. I'm an early starter, but as the deadlines piled on, this past week has been very hard. I've had no weekend at all for a while. Basically I had no time to study for the test until this thursday.
We've done no PS on it, no assignment on it, all we saw so far is a couple of examples in lecture, and very lengthy examples in the course notes. In situations like this, it's hard to know whether one's understanding of the topic is correct.
So, I still don't know if I even understand this topic enough, to do a seemingly elementary question like the one on the test. By contemplating the question more, on my way back home from the test I *think* I have a correct idea of what I should prove to prove termination. If I include the time during the test thinking about the question, that's about 40 minutes of thinking, to get an idea of what I think is a correct approach.
Essentially, the question was to me an assignment question that I had to do on a test.
I think it would have helped a lot if we were given more elementary examples, with clear explanations, on this topic. The posted past test had a question, but I didn't fully understand the solution either. The topic is not easy to understand, I think it warrants more examples than the ones we were given.
Maybe now after thinking about the test question I can look at the past test solution and understand it more. Though I doubt it. Probably have to go to an office hour, and spend a week thinking about it everyday and doing some practice questions to understand it. I wish I had the time this past week for that.
Saturday, November 1, 2008
Got hit on the head
For the grasshopper question... I wrote a proof of the recursive formula using combinatorics, and this lemma:
(n C r) = (n-1 C r) + (n-1 C r-1)
(n-1 C r) + (n-1 C r-1) = (n-1)!/r!(n-1-r)! + (n-1)!/(r-1)!(n-1-r+1)!
= (n-1)!/r! * 1/(n-r-1)! + (n-1)!/(n-r)! * 1/(r-1)!
= (n-1)!/r! * (n-r)/(n-r)! + (n-1)!/(n-r)! * r/r!
= (n-1)!(n-r+r)/r!(n-r)!
= (n-1)!n/r!(n-r)!
= n!/r!(n-r)!
= (n C r)
The proof I wrote was quite satisfactory. Then I got a very bright csc236 student to look at my code. He just hit me on the head with what he said: " How many ways can you jump to G(n)? only 2 ways".
ARRGH! Oh well it was good practice..
====
The material about proving preconditions => post conditions seems to be somewhat like a rigorous expression of what goes on in our heads when we write recursion or loops.
Although I definitely have trouble seeing the loop invariant component in proving the correctness of iterative methods. That part is not very intuitive for me. I'm having trouble finding the loop invariants that would assist in the proof. And, for that matter, don't know what I'm looking for either. Got some good tips at lecture how how to find them though.
Will have to go through lec notes and course notes extensively before the test. Gosh, what a busy week it's been, and what a busy week next week will be. For that matter, what busy months oct and nov are...
(n C r) = (n-1 C r) + (n-1 C r-1)
(n-1 C r) + (n-1 C r-1) = (n-1)!/r!(n-1-r)! + (n-1)!/(r-1)!(n-1-r+1)!
= (n-1)!/r! * 1/(n-r-1)! + (n-1)!/(n-r)! * 1/(r-1)!
= (n-1)!/r! * (n-r)/(n-r)! + (n-1)!/(n-r)! * r/r!
= (n-1)!(n-r+r)/r!(n-r)!
= (n-1)!n/r!(n-r)!
= n!/r!(n-r)!
= (n C r)
The proof I wrote was quite satisfactory. Then I got a very bright csc236 student to look at my code. He just hit me on the head with what he said: " How many ways can you jump to G(n)? only 2 ways".
ARRGH! Oh well it was good practice..
====
The material about proving preconditions => post conditions seems to be somewhat like a rigorous expression of what goes on in our heads when we write recursion or loops.
Although I definitely have trouble seeing the loop invariant component in proving the correctness of iterative methods. That part is not very intuitive for me. I'm having trouble finding the loop invariants that would assist in the proof. And, for that matter, don't know what I'm looking for either. Got some good tips at lecture how how to find them though.
Will have to go through lec notes and course notes extensively before the test. Gosh, what a busy week it's been, and what a busy week next week will be. For that matter, what busy months oct and nov are...
Subscribe to:
Posts (Atom)
