Today was the last day of the semester as well as test 3. It wasn't too bad; possibly Prof. Heap was taking it a bit easy on us since the final is only a week away. I spent a lot of time studying last night for it since I didn't get enough review earlier in the week since I was still finishing up projects and tests for other classes. I was glad to see no questions with the pumping lemma on it. Although I understand the idea behind it, I think I'd be shaky if I had to do a proof of it on my own.
I'm sure I've mentioned it in a previous post, but I think that this class was overly packed with tests, assignments and problem sets. Three tests was probably a bit much, but I guess it got people to attend class all the way till the last day.
Overall though I was happy with this course. Going in at the beginning I was definitely not too excited about it since I didn't enjoy CSC165. But I must admit that I enjoyed many aspect of the class and some of the material. So as the semester comes to a close, so does this blog. On to the final exam.
Friday, December 5, 2008
Week 11 and 12
Weeks 11 and 12 I'm sure were busy for everyone. As the semester draws to a close, students have assignments, essays and tests to do, and professors and TA's have stuff to mark.
Week 11 we saw a lot of NFSAs and equivalence. There was some tricky stuff to learn regarding the state invariants, and transition functions. We talked a lot about epsilon transitions, subset construction and equivalence. It was interesting to see the equivalence of the regular expressions and FSA.
Week 12 we looked at the pumping lemma. It became a useful tool to use to show that a language isn't regular. We used it in some examples; one which showed that the language of binary strings with equal number of 0's and 1's.
And finally we started to talk about the final exam and completed TA evaluations.
Week 11 we saw a lot of NFSAs and equivalence. There was some tricky stuff to learn regarding the state invariants, and transition functions. We talked a lot about epsilon transitions, subset construction and equivalence. It was interesting to see the equivalence of the regular expressions and FSA.
Week 12 we looked at the pumping lemma. It became a useful tool to use to show that a language isn't regular. We used it in some examples; one which showed that the language of binary strings with equal number of 0's and 1's.
And finally we started to talk about the final exam and completed TA evaluations.
Problem Set 6 - Problem Solving
Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)).
So I started this problem by reading and understanding the problem, simple enough step. I analyzed the regular expression in my head and jotted down some binary strings which were in the language L and compared them to the claim.
Since my test cases held, I began to try to think of some cases where a string in the language L didn't hold, but couldn't find any counter-examples. Next I began to think of ways in which I could prove this. I reread through some notes and figured that proof by cases would be best here. I then divided it up into two cases; Case 1: the string has length equal to 1 and Case 2: the string has length greater than 1.
I then went on to prove these two cases separately. At the end I reanalyzed my cases, wrote out a final copy and was done!
So I started this problem by reading and understanding the problem, simple enough step. I analyzed the regular expression in my head and jotted down some binary strings which were in the language L and compared them to the claim.
Since my test cases held, I began to try to think of some cases where a string in the language L didn't hold, but couldn't find any counter-examples. Next I began to think of ways in which I could prove this. I reread through some notes and figured that proof by cases would be best here. I then divided it up into two cases; Case 1: the string has length equal to 1 and Case 2: the string has length greater than 1.
I then went on to prove these two cases separately. At the end I reanalyzed my cases, wrote out a final copy and was done!
Subscribe to:
Posts (Atom)