Friday, December 5, 2008
Last Post : (
The last week comes to and end with a midterm test, I had no problems doing a test on the last day, the only challenge was getting here on time. But like usual , I was late again , almost 20 minutes , but luckily half of the material I was already prepared for , although I did have some difficulty proving the finite language question. Luckily since Danny's such a nice guy , he gave me some extra time , and I am very thank full for that (I hope I keep getting more teachers like him). Anyways so this course comes to and end ,although the exam is still left. Again , thank you Danny , I'll try my best not to be late for the exam. : )
Friday, November 28, 2008
Week 12 of CSC236
The second last week started off well for me , coming to class on time for once. But on Wednesday and Friday i reverted to my old habit of being late and now i am very confused about Context Free Grammar. Although i understand the concept and the meaning behind it, i am confused about a lot of the notation. Especially what S ==>*x means. Hopefully ill get this straightened up by the next midterm.
Monday, November 24, 2008
Week 11 of CSC236
Yet again this week is swamped. Along with 236 assignment and problem set, i also have my stats midterm , csc207 project. Because of this , there isn't very much i can do this week in terms of 236 , except the assignment and the problem set. Again i decided to work in a group because it would lighten my load as well as my partners'. Luckily we'll get the assignment done on time and properly, as for the problem set, i was planning on not doing it , but i managed to type it up the day before it was due, hopefully it'll be correct.
Monday, November 17, 2008
Fika's Dramatic Problem Solving Episode.
This will be my problem solving episode for the problem set 5. The problem is as follows :
Prove that if language L has a finite number of strings, then there is is some regular expression that denotes L.
After reading the statement a few times, my understanding of the problem is that we must show that a language with a certain number of strings , k , can be written with a regular expression of the form R+S , RS , or R*. But of coarse not all of the regular expressions can denote the language , so the problem was figuring out the suitable expression.
The next step in problem solving is devising a plan(s).This problem looked quite similar to the problem on page 193 of the text. The only difference is that the language in the book is defined to be infinite , rather than our finite case. So of coarse induction was the obvious way to proceed. By assuming that a language with k strings can be denoted by a regular expression , we could prove for a language with k + 1 strings. So using simple induction seemed like the ideal way to go , as it proved an important result in the base cases, which we will need and use later in the induction step. Complete induction could also have been used to prove this statement, but in simple induction I could easily the logic of combining regular expressions of a Language with k strings and a Language with 1 string.
Now to carry out my plan to prove the statement with simple induction. Of coarse when using simple induction we prove the base cases first. Since the cases where language is empty ,the language contains epsilon (the empty string) and a language with only 1 string are the interesting cases,I proved them in the base case. In the induction step, we assume that a language (L) with k strings can be denotes by the regular expression R. Now by constructing a new language with the language L , and an element x , we can create a language with k+1 strings. We know that L' = L + x , so we know that L' can be denoted by a regular expression R for the language L and a regular expression that denotes a string x, which by our base case we know exists. So by using our induction hypothesis , and our base case , we can construct L' by the regular expressions that denote L and the string x. Thereby proving that a language consisting of k+1 strings can be denoted by a regular expression.
Looking back at the problem, it was obvious that I could've proven the statement by using complete induction , or even structural induction. But I am confident that my solution is correct and using test languages , I could see that the union of regular expressions can denote any finite ( or infinite) language because by breaking the language into two pieces , I can create a regular expression for each portion of the language.
Perhaps this wasn't as dramatic as I first thought it would be , but I hope this gives the viewer some understand of the concept and I hope my solution didn't confuse anyone. This concludes the Dramatic Problem Solving Episode.
Prove that if language L has a finite number of strings, then there is is some regular expression that denotes L.
After reading the statement a few times, my understanding of the problem is that we must show that a language with a certain number of strings , k , can be written with a regular expression of the form R+S , RS , or R*. But of coarse not all of the regular expressions can denote the language , so the problem was figuring out the suitable expression.
The next step in problem solving is devising a plan(s).This problem looked quite similar to the problem on page 193 of the text. The only difference is that the language in the book is defined to be infinite , rather than our finite case. So of coarse induction was the obvious way to proceed. By assuming that a language with k strings can be denoted by a regular expression , we could prove for a language with k + 1 strings. So using simple induction seemed like the ideal way to go , as it proved an important result in the base cases, which we will need and use later in the induction step. Complete induction could also have been used to prove this statement, but in simple induction I could easily the logic of combining regular expressions of a Language with k strings and a Language with 1 string.
Now to carry out my plan to prove the statement with simple induction. Of coarse when using simple induction we prove the base cases first. Since the cases where language is empty ,the language contains epsilon (the empty string) and a language with only 1 string are the interesting cases,I proved them in the base case. In the induction step, we assume that a language (L) with k strings can be denotes by the regular expression R. Now by constructing a new language with the language L , and an element x , we can create a language with k+1 strings. We know that L' = L + x , so we know that L' can be denoted by a regular expression R for the language L and a regular expression that denotes a string x, which by our base case we know exists. So by using our induction hypothesis , and our base case , we can construct L' by the regular expressions that denote L and the string x. Thereby proving that a language consisting of k+1 strings can be denoted by a regular expression.
Looking back at the problem, it was obvious that I could've proven the statement by using complete induction , or even structural induction. But I am confident that my solution is correct and using test languages , I could see that the union of regular expressions can denote any finite ( or infinite) language because by breaking the language into two pieces , I can create a regular expression for each portion of the language.
Perhaps this wasn't as dramatic as I first thought it would be , but I hope this gives the viewer some understand of the concept and I hope my solution didn't confuse anyone. This concludes the Dramatic Problem Solving Episode.
Week 10 of CSC236
Again being late has put me a little behind for the Monday class, but luckily DFSA's aren't that hard to understand , and I find them creepily interesting. I had to teach myself what the notations d(q,a) meant exactly, but luckily Prof. Heap's notes are very easy to understand, but sadly the book isn't quite clear on this chapter. But I think I taught myself well enough to understand the notation. Creating the DFSA's is also eerily fun, also its very good at explaining the states of the Languages and strings.
On Friday I was quite pleased to get my test and problem set 4 back. I genuinely though I had messed up the last test, but to my pleasant surprise I did quite well , at least a lot better than I thought I would. Hard to believe its already week 10 , the school days go by so fast. Sadly this was my only "free" week this semester , but luckily we only have 3 more long weeks left of school remaining.
On Friday I was quite pleased to get my test and problem set 4 back. I genuinely though I had messed up the last test, but to my pleasant surprise I did quite well , at least a lot better than I thought I would. Hard to believe its already week 10 , the school days go by so fast. Sadly this was my only "free" week this semester , but luckily we only have 3 more long weeks left of school remaining.
Saturday, November 8, 2008
Week 9 of CSC236
In the beginning of the week it seemed very odd to me to prove properties of strings in "Languages". But when i started to look at it as if the languages were methods or predefined parameters etc , it made sense that combining these strings can help show some properties of some language.
Luckily I was on time this time , a few minutes earlier in fact , for the test. The test itself wasn't too difficult , except the last question. The only reason I had trouble with it because of the minimal time I spent studying csc236 because of my calculus test. But still hopefully I will do adequate on the test, we will see next week.
Luckily I was on time this time , a few minutes earlier in fact , for the test. The test itself wasn't too difficult , except the last question. The only reason I had trouble with it because of the minimal time I spent studying csc236 because of my calculus test. But still hopefully I will do adequate on the test, we will see next week.
Monday, November 3, 2008
Week 8 of CSC236
After a very stress filled and a packed weekend I finally managed to get the A2 done. I decided to work in a group to lighten my load as well as my partners' load as well since we all had a tonne of other things due. I wrote the good copy of the problem set the night before just because I could not get any time to start on it anytime earlier. Although it was easy , it still took me some time to write it up properly as my rough work was very , well rough.
Loop iteration isn't very hard especially when you figure out the precondition and postcondition, but thats where the problem lies for me. I find it difficult to come up with a suitable precondition , especially if its a function like pow , where the conditions are very trivial which makes them hard for me. Hopefully ill understand loop invariants a little better by the end of the week after my very busy week.
Loop iteration isn't very hard especially when you figure out the precondition and postcondition, but thats where the problem lies for me. I find it difficult to come up with a suitable precondition , especially if its a function like pow , where the conditions are very trivial which makes them hard for me. Hopefully ill understand loop invariants a little better by the end of the week after my very busy week.
Subscribe to:
Comments (Atom)
