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!