Problem Set 6

This problem set involved proving an implication (if-then statement). We had to prove that if a language L consists of odd length binary strings, then it can be denoted by ((0+1)(0+1))*(0+1). I used the idea of inclusion for both directions. That is if T is the set of all odd length binary strings, then an element belonging to T must also belong to L(((0+1)(0+1))*(0+1)). To prove this direction, I started off with an odd length binary string and constructed the regular expression that would denote it, step by step. In the end I was left with the expression ((0+1)(0+1))*(0+1)), thus proving the implication in one direction. The other direction is proving that if an element belongs to L(((0+1)(0+1))*(0+1)), then it must belong to T. To prove this direction I broke the regular expression into its even and odd components, and showed that the concatenation of both components yields an odd length binary string. This prove seemed to be pretty lengthy but it was straightforward.