Week 11 Still: Polya Problem Solving Episode!

I've decide to write up a problem solving episode of how I solved Problem Set #6.

Problem: Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)).

1) Understanding the Problem:

In class we were shown the process for proving a language equivalency question such as this, and what it boils down to is proving mutual inclusion: that if x is in L then x is in L(((0+1)(0+1))*(0+1)) and if x is in L(((0+1)(0+1))*(0+1)) then x is in L, for any arbitrary string x. So this question is really doing two shorter proofs and using them to make one larger claim.

2) Devising a Plan:

The best way to plan out this proof is to use the structure that was presented in lecture and in the textbook. This structure consists of first proving each inclusion separately, by taking an arbitrary element of one of the languages and breaking it into sub strings then recombining those sub strings and showing that they meet the criteria for the other language.

To do this, it would be best to split each arbitrary string into sub strings based on the amount of characters, not specific characters. I think this would be best because all we need to know is that the string has an odd length, and the generic odd number is 2k+1 where k is some natural number. In fact this formula for odd numbers gives me some insight into how to prove it: break the string into k sub strings with 2 characters and then a suffix of 1 character. The good thing about this idea is that it it is the same format as L(((0+1)(0+1))*(0+1)) - replacing (0+1) with one and the Kleene star with a k give the definition of odd: (1+1)k+1 = 2k+1.

Now that I've discovered how to go from one language to the other I just have to write it up in a formal manner.

3) Carrying out the Plan:

Let x be an arbitrary element of L(((0+1)(0+1))*(0+1)). Then there exists some k e N, and y_0,y_1,...,y_k e {0,1}* such that y_0 e L(0+1) and y_i e L((0+1)(0+1)) for all 1 <= i <= k.
Then for each y_i for 1 <= i <= k has two characters - 0 or 1 followed by 0 or 1 - so 2k characters total, when concatenated together in the form y_1y_2...y_k.
Also, y_0 has exactly 1 character - 0 or 1 - so y_1y_2...y_k_y_0 concatenated together has 2k+1 characters, an odd number. Thus x, represented by y_1_y_2...y_k_y_0, has an odd length and thus is an element of L.

Let x be an arbitrary element of L. Then by definition x has an odd number of characters (an odd length), lets say 2k+1 characters for some k e N. Now we can define k consecutive sub strings of x, where for each i, 1 <= i <= k, y_i is the sub string of x from the (2i-1)th character to the (2i)th character, both inclusive.
Thus each y_i e L((0+1)(0+1)). Also, let y_k+1 b the last character of x, the (2k+1)th character. Then y_k+1 e L(0+1).
Nowe we have defined x = y_1y_2...y_ky_k+1 concatenated, where each y_i e L((0+1)(0+1)) for all i, 1 <= i <=k, and y_k+1 e L(0+1).
Therefore, x e (L((0+1)(0+1))^k)(L(0+1)) which is a subset of L((0+1)(0+1))*L(0+1) = L(((0+1)(0+1))*(0+1)). Thus it follows that x e L(((0+1)(0+1))*(0+1)).

We have proven that x e L ==> x e L(((0+1)(0+1))*(0+1)) and x e L(((0+1)(0+1))*(0+1)) ==> x e L. Thus they are mutually inclusive and therefore equivalent.

4) Looking Back:

The key to proving that one language is equivalent to another seems to be how I seperate each language into its basic parts and relate them to eachother, informally seeing why they are indeed equivalent.

Week 11: A3 and being tired.

So far I've spent all day on Assignment #3, and started this assignment about a week ago. I've managed to finish everything except question 3, which I really don't want to do because it looks very complicated. This assignment is really wearing me out. And it doesn't help that I don't have any time to go to office hours - studying for midterms, working on my CSC207 project, doing STA247 homework assignments, trying to figure out what's going on in linear algebra, it all never ends.

At least I sort of understand what's going on this course.

Week 10: Happier

I did considerably better than I thought on Term Test #2, so that brought up my confidence. In addition to that I'm not having as many problems as usual with this assignment, although it would be much easier if the textbook gave a proof from why (0*1*)* = (0+1)*. I know why informally, but trying to prove it seems rather difficult so I hope its more of a lemma that I could site in my assignment.

I've also been looking at the bulletin board challenge thread, trying to come up with counterexamples to the regular expressions people have come up with. Sometimes I do, sometimes I don't, but overall it feels like good practice.

Edit: Upon going to office hours, I've been informed that I would indeed have to prove (0*1*)* = (0+1)*. It seems like a hassle to prove, so I might just have to go the long way and prove each part of question two on Assignment #3 separately.

Week 9: Hm..

I didn't do as good as I hoped I would on the second term test, for the 3rd question I couldn't think of what the loop invariant would be, although now I think it must be something like "n is a natural number". Classes haven't been going very well, and all this regular expression stuff is very confusing. I'm not sure what to do, even the latest problem set is hard, I have no idea how to approach it.

University is depressing.

Update: Making a post while depressed isn't a good idea. Problem Set #7 wasn't hard at all, and since I'm also doing regular expressions in CSC207 it dosen't seem to be too bad anymore. Also, Assignment #3 is going well and I actually enjoy doing the Finite State Automata questions.

Week 8: Confused

Having so much work to do each week is getting me confused with what's going on in CSC236. All the recent stuff that we have been learning, about the Master Theorem and proving the complexity of recurssive programs or loop invariants is pretty hard to understand. And the book dosen't help at all, it has pages and pages for just a single proof and things thrown in the middle like "Oh yeah, and you need to know this fact to solve this proof". It's sort of getting m worried for Term Test #2, I'd really like questions to be posted similar to questions that we do for Problem Sets for some practice before the test. At this point all I can really hope is that on Monday we'll get a slight list of things we need to know for the test. I don't like having to study the assignments for tests, since our assignment questions are always so long that its hard to see how any question could be on the test.
Will we get a little program and have to write a recurssive formula for its time complexity and then prove it right? Or will we just be given the formula and prove a closed form of it? Will he have to prove some sort of loop invariant? Or that a precondition implies the post condition of some function? My normal way of studying is to think about all the possible structures of questions that could be asked and study the ways of solving them before hand, but as of right now I'm not sure how I'd do that for this test.
Oh well, hopefully I'll have time to start studying on Tuesday.