week 13/ test 3

Just had test 3 this week. Question 1 was ok. Just had to spend time to trace the various states. As for the first part, there was a pattern apparently. Question 2 and question 3 were rather similar to what we did in lectures. I used structural induction for the "infinitely many strings/1,0" question and for proving the equivalence, i used an approach similar to what danny did. Prove that each is a subset of another. Correct? I know i'll lose marks here and there but i hope it's ok. Didn't attend lecture today after the test. Only 1 hour of sleep the previous night studying for T3. CSC236 tests worry the hell out of me everytime.

week 12 - A3/ Non-Regular Languages Pumping Lemma

A3 was due this week. For me, it seemed as if i managed to find a counter example for all parts of Q2. It seems like there is at least 1 regex that did not exist in the language. It can't possibly be all false. Don't think A3 will go as well now. And as for the DFSA question, it's a pain to have to type the notations. I didn't even know if my notations are correct of what format the question wanted. How do u draw a picture of the DFSA using .txt? Oh man...i must be missing something here. Pen and paper please!!!

week 11 - NFSAs, Equivalence

Finally after reading through the notes for DFSA, I've figured out the how the DFSA works and i've also finally understood the example about strings that are multiples of 3 in base 2. Sounds complicated, but actually it's quite easy. But to design a DFSA will require careful thought to ensure nothing is left out.

This week we did NFSAs and equivalence. Proving the DFSA sounds straightforward. Just start with the base case that all portions of the state invariant are true, then go on to use x=x'a, a concatenation of strings, to show that the property is preserved. Structural induction in this case? We have to show that starting from a smaller substring x', we arrive at the same state invariants for x as well.

As for NFSA, i have to read up on that. All that NFSA set of states vs DfSA sets is confusing me. We also did cartesian product. It's like a pair of DFSAs to be combined in to one. It's not all that bad.

BUT for regular expressions, the example for even #of 0s and odd # of digits was not all that clear. After removing q_11, why did the transitions linking q_00 to q_01 and q_01 to q_00 change from 1 to 1+01(11)*10? Since q_11 was only linked to q_00 and q_01, why did the transitions from q_00 to q_01 get affected when it was removed?

Problem Solving Episode

So here goes my problem solving episode:

Question is Q3 from A3.


Prove that any regular expression that doesn't include a Kleene star denotes a 􏰀nite language.

1. UNDERSTANDING THE PROBLEM

We are supposed to prove that any regular expression that does not contain a * denotes a finite language. This sounds rather straightforward but it's difficult to put in words. The data we have is a regex and finite language. Condition is that any regex that does not contain a * denotes a finite language. We can easily satisfy the condition by assuming a regex without a *. The unknown is the language that we have to show is finite. Condition should be able to determine the unknown.

2. DEVISING A PLAN

First, a regex can be connected to a language. regex denotes a set of strings, just like a language by definition. So a string is made up of a finite number of symbols. Then the plan is to link the finite number of symbols to a string and this can be linked to a regex and then a language. But is this correct? The post on the bulletin board gave some crucial hints.

Seems like we can use structural induction to carry out this proof. We can start from the basic set and show that it satifies the condition that regexes without * will denote a finite language. Then we can carry on to say that 2 regexes that do not contain * will also denote 2 finite languages.

3. CARRYING OUT THE PLAN
Basis will be to show that a regex without a * will denote a finite language. We can use one symbol to show that it denotes a language with just 1 element. So it will be finite.
Then for the induction step: We can show that if 2 regexes(R,S) denotes 2(L(R),L(S)) languages, then by the IH, it will be finite as well. We shall make use of the properties of languages that L(R+S) = L(R) U L(S) and L(RS) = L(R)L(S). So since L(R)+L(S) and L(R)xL(S) are both finite, then we can conclude that any regex that does not contain * will denote a finite language.

4. Looking Back
By using structural induction, we started from the basic set and showed that it's true. Since by making use of the properties of L, structural induction is a powerful tool to show that L1+L2 contains what the IH showed. So this argument should make some sense. Not too sure if there is another way to solve this problem though.

We might also want to try to use the fact that a string is made up of a finite number of symbols and if we can link that fact to regexes without * and ultimately we might be able to use that to denote a finite language.

This concludes my problem solving episode!

week 10 -Regexes, FSAs

This week we did DFSA and a little of regex algebra. I wonder how important regex algebra will be in this course. But as for DFSA, I didn't really understand what the state invariant meant. But after i read the course notes and understood it better. It's just like a description and it describes how the system moves from the initial state to another state.

However, i didn't really get what the example with the multiples of 3 in base 2 meant. Shall have to go through the part about the x1 and x0 parts again.

week 9 - Formal Languages

For week 9, we had a term test. I was initially quite worried about the test. Had to revise the material over and over again before the test. It doesn't help if i have to work on Thursdays before lecture. But luckily i had time to go through the material one last time before the test. It turned out that the test was ok. The last question did not work out too well but it was ok. I think i forgot to read the last question properly. But it's work 2 marks so hopefully it will not hurt the overall score too much.

During lecture, we did formal languages. So a set of strings is a language. Strings consist of symbols from an Alphabet. Then a language consists of a set of all possible string over the alphabet. So a language is a subset of the alphabet?

Again, nothing made sense during lecture. Had to re-read the slides after i got home. Something confused me a little. For the equality of languages, the example we did was to prove that L1 = {x has an even number of zeros} and L1 = (1*(01*01)*). For Xi, why is the substring starting at (2i-1)and ends at the (2i+1)th 0? Why 2i? Shall ask Danny when during office hours then.

week 8- iterative correctness

was quite confused about this week's lecture. Didn't understand the part about 7m+n=7a+b+i. The proof made a little sense to me but i just didn't understand the 1st part. This proof is rather similar to that of the previous week's proof. Just this time we have to count the i-th iteration in as well.

Do we have to make use of PWO at this point? To show that at the next iteration, we will always end up with a smaller variable and it will get smaller and smaller until it reaches 0. Is that how we are supposed to make use to PWO? How to apply PWO in this case?

A2 was a disaster. It took way longer than i expected. So as a result i did not finish it. But come to think of it, it was quite impossible for me to finish it. With 2 midterms on 22 and 23, 207 E3 and a group report due on monday then followed 207 midterm on wednesday, it was quite a challenge to finish my work on time. Just bad bad planning on my part.

I know danny reads our blogs...some help maybe? Haha. But oh well..can't ask for anything since i am responsible for my own work. Just hope to survive this course..........

week 7 - program corectness

Program correctness was taught this week. Proving correctness seemed rather straight forward. From what i understand, the key is to go slow and go line by line. We start at line 1 of the code and then probe deeper into the chunk of code. Since PS4 is about proving a python program, this is what i am going to do. I will start at the first line, and then just explain what the code will do at each iteration. It's rather similar to that example danny did in class but just not that complex. I just have to make sure my proof satisfies the postcondition.

We also did GCD. Nothing much to say about that.

Luckily PS4 is going to be due on monday instead. If not, with tests on wednesday and thursday, i wonder if i will complete PS4 on time without the extension.

week 6 - complexity of merge sort master theorem

This week we had a shorter lecture due to Thanksgiving. The proof of mergeSort looks simple. Again..it's Danny who is doing it. But after reading it over and over again, it makes more sense now. We also did the Master Theorem, a kind of strategy that works somewhat like the mergeSort. We divide a problem into smaller components then combine solutions. Since the solutions are now split up into smaller parts, it should be easier to solve.

But the question is, how to apply the general theorem? on slide 9 there T(n) is equal to 3 different formulas depending if its value relative to b^l.

Now for PS3, after reading the hint for PS3, it was a little easier to write out a proof. Just kept unwinding and unwinding. It's just a sum of 3^n, n starts at 0. I shall use that as a starting point for my proof then. Another PS done. 3 more PS and many many more tests to go.

week 5 - closed form of recurrence, structural induction, gcd

Just finished test 1 this week. I was so worried about test 1 since i had no clue about most of the material. I studied and studied a week ago but still felt that i was not properly prepared. But fortunately, the test was fair. Phew.

I did not attend lecture today since i really needed some sleep after studying all night for the two nights before the test. Too tired to attend lecture.

week 4 - recursive definitions

A1 was quite bad for me. Could not figure out how PWO worked for the golden ratio question. Luckily the bulletin board provided some answers. I won't expect much for A1 now. The second question about the repeating menus is interesting. I figured out the cycle for the 3 meals. But a technique? Whao...i feel stupid for not being able to answer that. Perhaps i started really really late. That's why i don't have enough time to figure it out.

Evening lectures are killing me. But i don't want to make the blog to vent my frustrations. I should use this blog as something to describe my experience for 236. I'll try to stop doing that now.

This week we did recursive definitions. As usual, i had no idea what danny was talking about during lecture. I did some reading up back at home and found that it was not as bad as it seems.It's all about unwinding etc...but i am rather confused about base cases. When do we need 2 or more of them? Oh well maybe i will ask danny when i have the chance to visit him during office hours. I need to check with him about my PS1 too. I think the TA lost it!!! I didn't get a grade for PS1. :(


ok hell season is officially starting for me. Starting from next week, i will have tests and assignments due every week and i am not only talking about 1...at least 2 per week. Let's hope i can keep up with my csc236 work. Test 1 is coming up next week too. I have to start early this time.

Week 3 - Principle of Well-Ordering Equivalence of induction flavours Traps and tricks

It's a little late, but finally i have the time to update my blog. Just not used to doing this.

This week we did PWO during lecture and i had simply no clue about the round robin example. It sounds logical, but then it is hard to implement. Danny always makes it sound easy but when i try to do it, i am lost. But i did some reading on PWO and hopefully it is not as bad as i think it is. Simple and Complete induction sounds better.

A1 is due tomorrow and i have yet to start. I think it will be another disaster. I'll try my best though but i need more time. Was too lazy to start and now i have to bear the consequences.
Semester is not starting well at all...

1st lecture...induction

Was late for my 1st lecture as i thought the class was from 7-9pm. The timetable stated that lecture was from 7-9 and there are no tutorials on the 1st week on school. Well for some reason i am clearly wrong. And i missed the 1st hour of lecture..not a good way to start..

It's been a long long time since i took csc165 and i HATED it. I absolutely suck at these things. These things never made sense to me. But also i had a bad prof at UTM for csc165. After taking a look at the course outline, i was shocked at the amount of work for this course. But as with any other math course, practice makes perfect so it's good i guess..especially if i am not good with these techniques..

This course will be a challenge to me though. But i hope i can overcome this and survive!

My first blog and it's for csc236??

Hi, welcome to my blog. Or Slog. It's part of a courSe log for my class. That's where slog came from.For those of u who are not in the csc236 class, U probably should not be reading this as it's gonna be boring! :P

This is my 1st time blogging and i've never understood the point of getting a blog anyway. So u can say that i've been forced to blog for the sake of getting a better grade in my course. Nevertheless, it's creative of the professor to think of this idea. And this is not even a writing course. It's supposed to be a math based course. Well i guess the professor has his reasons for making us have our own course blogs. Perhaps it's a way of giving feedback and also it can help me check if my peers are experiencing the same things. But that's provided i read the rest of the blogs!

It's still too early to tell if the blogs will be useful to our learning experience but it's a completely new idea for a math course and we'll see later if this works to our advantage....