Date: This Friday
Today we moved on to what we do best, proving that the context-free grammar works. The one grammar we are proving in the lecture denotes the set of binary strings having the same number of 0s and 1s.
The proof itself is not hard, but extremely long (just like proof of correctness and the proof of the DFSAs/NFSAs). Not to mention the random Intermediate Value Theorem jumping in out of nowhere to save the day (it works perfectly with this proof), that really surprises me.
I'm still enjoying my relatively free week to study before the exam storm brew, 4 consecutive exams, with my first two exams (back-to-back - right after each other) on the first day.
Oh, scratch that! I'll have to find time in the midst of studying to do well in the third test/think up a problem solving question for this Slog, not to mention 207 project in its final phase... there's still quite a lot of things to keep me busy these days...
Saturday, November 29, 2008
Wednesday, November 26, 2008
New lesson
We finished with all the regular expressions and formal automata stuff, now we moved on to context-free grammers.
Everything's still related, with the grammer taking in variables, terminals, production and start states similar to the DFSA/NFSA material. I liked how you can express many strings in the language this way, it is also very fun but tricky like the exercises for today.
I'm still enjoying my rare workload-free week, I plan to start studying for the third test during the weekend.
Everything's still related, with the grammer taking in variables, terminals, production and start states similar to the DFSA/NFSA material. I liked how you can express many strings in the language this way, it is also very fun but tricky like the exercises for today.
I'm still enjoying my rare workload-free week, I plan to start studying for the third test during the weekend.
Monday, November 24, 2008
It's all over (I guess?)
Bad day, bad day, bad day >_<
First, there's phase 3 for the 207 project due in the morning, second, there's stat problem set to hand in, third, assignment 3 for this course. I have to cope through the whole day with massive sleep deprivation.
Back on topic, today we learn the definition of non-regular languages, what surprises me the most is the fact that there are more non-regular languages than regular languages, as well as the fact that the alphabet we are using (binary digits of 0 and 1) was not even regular at all!
As well, the pumping lemma. I also raise the question about the "lemma" alongside with Danny, because to me it seems very important in this topic. The pumping lemma is useful to determine whether a language is regular or not, as well as its simplicity, both in diagram and definition. I also find it rather funny how you can "pump" a language to make it irregular.
Now that most of the workload is done, with two more weeks to go, I'll catch up on the study, get more sleep, and prepare for the final exams during December.
First, there's phase 3 for the 207 project due in the morning, second, there's stat problem set to hand in, third, assignment 3 for this course. I have to cope through the whole day with massive sleep deprivation.
Back on topic, today we learn the definition of non-regular languages, what surprises me the most is the fact that there are more non-regular languages than regular languages, as well as the fact that the alphabet we are using (binary digits of 0 and 1) was not even regular at all!
As well, the pumping lemma. I also raise the question about the "lemma" alongside with Danny, because to me it seems very important in this topic. The pumping lemma is useful to determine whether a language is regular or not, as well as its simplicity, both in diagram and definition. I also find it rather funny how you can "pump" a language to make it irregular.
Now that most of the workload is done, with two more weeks to go, I'll catch up on the study, get more sleep, and prepare for the final exams during December.
Sunday, November 23, 2008
Ack!
Date: Friday
Apparently I'm not good at keeping track, it is now Sunday (when I'm writing this).
Today lecture is similar to the lecture we did a few weeks ago regarding how PWO, PCI and PSI relates to each other, we started first by deriving a regular expression given a DFSA, and show that how regex, NFSA, and DFSA also has very close relationships with each other.
I still have trouble grasping the purpose of epilson transitions in NFSA, is it just some kind of a placeholder?
I haven't started working on assignment 3 yet, I looked at it a long time ago, thought about it, but haven't written any conceivable proofs regarding it. It doesn't seem that hard, I just have trouble formulating the definition of the Kleene star (question 3) in the head, and how I should go about to prove it. Right now, I'll take a rest - a brain's always clearer when you're not tired.
Apparently I'm not good at keeping track, it is now Sunday (when I'm writing this).
Today lecture is similar to the lecture we did a few weeks ago regarding how PWO, PCI and PSI relates to each other, we started first by deriving a regular expression given a DFSA, and show that how regex, NFSA, and DFSA also has very close relationships with each other.
I still have trouble grasping the purpose of epilson transitions in NFSA, is it just some kind of a placeholder?
I haven't started working on assignment 3 yet, I looked at it a long time ago, thought about it, but haven't written any conceivable proofs regarding it. It doesn't seem that hard, I just have trouble formulating the definition of the Kleene star (question 3) in the head, and how I should go about to prove it. Right now, I'll take a rest - a brain's always clearer when you're not tired.
Wednesday, November 19, 2008
Pointless entry
Ah, so I finally understands what NFSA is, and how it relates to DFSA in today's lecture.
The massive amounts of epsilon transitions confuses me a little, but everything makes sense with a picture of a FSM.
Still cannot grasp the ideas behind many of the regular expression symbols, but it should be cleared when I worked through problem set 6 and assignment 3.
Should start on both above-mentioned work.
The massive amounts of epsilon transitions confuses me a little, but everything makes sense with a picture of a FSM.
Still cannot grasp the ideas behind many of the regular expression symbols, but it should be cleared when I worked through problem set 6 and assignment 3.
Should start on both above-mentioned work.
Monday, November 17, 2008
A new week
Due to my poor eyesight for today, I'm unable to write everything down, so I'll recall with my memory of today's lecture.
So we started to prove that a Deterministic Finite State Automata (DFSA) is correct given what the machine supposed to do and a proper string in the alphabet. The prove itself, like the proof of correctness, is rather long but not hard.
Next, we went on to the definition of NFSA (what's the N stands for anyways?), which I (unfortunately) can't see too clearly what it is about, I assume it is quite similar to that of the DFSA.
I'll take a break today, got to rest my eyes.
So we started to prove that a Deterministic Finite State Automata (DFSA) is correct given what the machine supposed to do and a proper string in the alphabet. The prove itself, like the proof of correctness, is rather long but not hard.
Next, we went on to the definition of NFSA (what's the N stands for anyways?), which I (unfortunately) can't see too clearly what it is about, I assume it is quite similar to that of the DFSA.
I'll take a break today, got to rest my eyes.
Saturday, November 15, 2008
second midterm....
Date: Friday
I see a pattern correlating with me and the midterm (of all kinds):
- When I'm not confident, when I feel I'll do bad on it, the mark generally are higher than what I expected.
- When I'm confident, when I feel alright about the midterm, the mark is lower than what I expected (well... not really, just lower then average... overall).
I don't get it, so maybe I'll just stay insecure about every kind of of written exam, there's much more improving I needed to do to get better on it.
Today's class is gone basically into course evaluation and handing back problem sets and midterms, since there are not much to write about on Friday, I'll finish here.
I see a pattern correlating with me and the midterm (of all kinds):
- When I'm not confident, when I feel I'll do bad on it, the mark generally are higher than what I expected.
- When I'm confident, when I feel alright about the midterm, the mark is lower than what I expected (well... not really, just lower then average... overall).
I don't get it, so maybe I'll just stay insecure about every kind of of written exam, there's much more improving I needed to do to get better on it.
Today's class is gone basically into course evaluation and handing back problem sets and midterms, since there are not much to write about on Friday, I'll finish here.
Wednesday, November 12, 2008
FSAs
I think I finally can grasp the usage and idea behind regular expressions now, so I think this will propel me quickly in understanding the lecture.
Today's class is rather interesting - more deterministic finite state automata, it was so interesting that I might just search for the same program that Danny used in the class today and the previous lesson before that.
But the darker side, I'm still a bit confused about the definition of language and a set of alphabets (afterward when I'm doing my problem set 5 I finally understand the difference between them), so there's hopefully no problem with this topic from now on. All I need is to spent time wisely and catch up with my work.
Today's class is rather interesting - more deterministic finite state automata, it was so interesting that I might just search for the same program that Danny used in the class today and the previous lesson before that.
But the darker side, I'm still a bit confused about the definition of language and a set of alphabets (afterward when I'm doing my problem set 5 I finally understand the difference between them), so there's hopefully no problem with this topic from now on. All I need is to spent time wisely and catch up with my work.
Monday, November 10, 2008
*Sigh*...
I've suffered a major sleep deprivation today finishing off A2 for 207, sleeping at 4 a.m. and waking up at 8 a.m., not that it's a big deal for other people (who I guess have experienced worst) who had been through this many times, but I just don't feel like myself today.
Strangely, it's the opposite that happened. Usually I'm awake mentally but tired physically, but today I felt I can stay through the lecture without completely collapsing mid-way through the lecture, yet I have trouble concentrating mentally, oh well... this happens only today I guess...
The lack of practice for today's topic (regular expression/finite state automata) certainly had me at a loss yet again, this is amplified more by the lack of sleep explained above. With enough time (I still haven't studied for the MAT 223 quiz on Thursday yet) I'll have to try harder reviewing those to get a better grasp of this and prevent me from falling seriously behind.
Then there's another problem set, oh great..., well..., at least my workload eases up a bit after this week.
Minor complaint here: It just seemed like this course, together with STA 247, has been giving us weekly work throughout the semester, it's hard as it is for me to went through this (plus other courses) without a break or a two in between, plus I'm behind in all of my courses yet again, oh time... you are certainly very elusive when I need you.
Strangely, it's the opposite that happened. Usually I'm awake mentally but tired physically, but today I felt I can stay through the lecture without completely collapsing mid-way through the lecture, yet I have trouble concentrating mentally, oh well... this happens only today I guess...
The lack of practice for today's topic (regular expression/finite state automata) certainly had me at a loss yet again, this is amplified more by the lack of sleep explained above. With enough time (I still haven't studied for the MAT 223 quiz on Thursday yet) I'll have to try harder reviewing those to get a better grasp of this and prevent me from falling seriously behind.
Then there's another problem set, oh great..., well..., at least my workload eases up a bit after this week.
Minor complaint here: It just seemed like this course, together with STA 247, has been giving us weekly work throughout the semester, it's hard as it is for me to went through this (plus other courses) without a break or a two in between, plus I'm behind in all of my courses yet again, oh time... you are certainly very elusive when I need you.
Saturday, November 8, 2008
Reflections on the second midterm
Date: Friday
I still didn't do quite well, but at least I'm more confident in my proofs now having been through two months of inductive proof training. The reason why I didn't get a chance to finish writing up the midterm is because I spent way too much time on question 2 - trying to make sure all the cases work. I managed to find the loop invariant and write out the proof structure, but I handed the midterm in early because I figured there's nothing you can do in less than 1 minute. Question 1 otherwise was easy and relatively straightforward, yet I tripped myself a bit (overwhelmed?) at the beginning when I couldn't figure it out.
I just hope that I can continually to improve all the way to the exam.
I still didn't do quite well, but at least I'm more confident in my proofs now having been through two months of inductive proof training. The reason why I didn't get a chance to finish writing up the midterm is because I spent way too much time on question 2 - trying to make sure all the cases work. I managed to find the loop invariant and write out the proof structure, but I handed the midterm in early because I figured there's nothing you can do in less than 1 minute. Question 1 otherwise was easy and relatively straightforward, yet I tripped myself a bit (overwhelmed?) at the beginning when I couldn't figure it out.
I just hope that I can continually to improve all the way to the exam.
Wednesday, November 5, 2008
The proofs of regular expression
Such a wonderful topic...
Yes, I need to get myself acquainted with the definition of regular expression/formal languages first before re-reading the lecture notes to fully understand it.
We did the mutual exclusion of binary numbers 0 and 1 for x \in L1, X \in L(1*(01*01*)*). The amounts of *s, 0s, and 1s really make me uncomfortable, so does all other regular expression I've seen so far.
Oh well! Guess I need practice, but first I need to make sure I prepare myself well for the next term test ahead.
Yes, I need to get myself acquainted with the definition of regular expression/formal languages first before re-reading the lecture notes to fully understand it.
We did the mutual exclusion of binary numbers 0 and 1 for x \in L1, X \in L(1*(01*01*)*). The amounts of *s, 0s, and 1s really make me uncomfortable, so does all other regular expression I've seen so far.
Oh well! Guess I need practice, but first I need to make sure I prepare myself well for the next term test ahead.
Monday, November 3, 2008
First entry in November
I kind of forgot that the daylight saving actually was moved to last week in October, so I guess this has a bit of side-effect regarding my physically wellness...
Leaving that aside, we started November with a brand new topic - formal languages. Having briefly skimmed through the near-end of the textbook, the mass amount of symbols is extremely daunting. I felt a bit of relief from today's lecture, where we started everything from scratch.
We were exposed with the definition of alphabets (a set of symbols that is undividable, denoted capital sigma), string (a finite sequence of symbols from capital sigma), and language (all possible strings over capital sigma to capital sigma star), as well as various operations regarding them.
We also get started on regular expressions (the basic definition really) before the time is up. Despite being tired, I still managed to absorb most of the lecture in my head. I find the proof for this type of topic will be interesting, especially when you treat strings (or characters) as normal real/integer numbers.
I find this course to be very beneficial to future computer scientists, from learning the various ways of proving using induction, recursion/iterative proves, correctness proof of programs to this topic (programming languages) and more stuff to come (chapter 8 stuff?), it will surely prepare future computer scientists with a number of important skills that they need.
Leaving that aside, we started November with a brand new topic - formal languages. Having briefly skimmed through the near-end of the textbook, the mass amount of symbols is extremely daunting. I felt a bit of relief from today's lecture, where we started everything from scratch.
We were exposed with the definition of alphabets (a set of symbols that is undividable, denoted capital sigma), string (a finite sequence of symbols from capital sigma), and language (all possible strings over capital sigma to capital sigma star), as well as various operations regarding them.
We also get started on regular expressions (the basic definition really) before the time is up. Despite being tired, I still managed to absorb most of the lecture in my head. I find the proof for this type of topic will be interesting, especially when you treat strings (or characters) as normal real/integer numbers.
I find this course to be very beneficial to future computer scientists, from learning the various ways of proving using induction, recursion/iterative proves, correctness proof of programs to this topic (programming languages) and more stuff to come (chapter 8 stuff?), it will surely prepare future computer scientists with a number of important skills that they need.
Saturday, November 1, 2008
Discrepancy
Date: Halloween Friday, supposedly this post should belong to the October posts but oh well...
The end of the eighth week gave us the hardest part of correctness proving - the nested loop. Even staying focused for this lecture doesn't help, as I'm hopelessly lost in finding ways to understand it. First of all, I'm enormously distracted by other assignments/problem sets due next week to even bother reviewing for the second term test next week. Second, my understanding of loop invariant is not sufficient enough - I thought that it is some variable staying unchanged throughout the loop, using it to prove the postcondition certainly had me going back to re-understand this stuff (if I got the time for it). And lastly, as I stated in previous posts that it will take awhile for me to understand and prove correctness for iterative loop - especially the part about finding a decreasing sequence that will make the loop terminate.
So much stuff to do yet so little time, ah... certainly I need to spent time wisely from now on...
The end of the eighth week gave us the hardest part of correctness proving - the nested loop. Even staying focused for this lecture doesn't help, as I'm hopelessly lost in finding ways to understand it. First of all, I'm enormously distracted by other assignments/problem sets due next week to even bother reviewing for the second term test next week. Second, my understanding of loop invariant is not sufficient enough - I thought that it is some variable staying unchanged throughout the loop, using it to prove the postcondition certainly had me going back to re-understand this stuff (if I got the time for it). And lastly, as I stated in previous posts that it will take awhile for me to understand and prove correctness for iterative loop - especially the part about finding a decreasing sequence that will make the loop terminate.
So much stuff to do yet so little time, ah... certainly I need to spent time wisely from now on...