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.