Week 10

Try to prove L(((0 + 1)(0 + 1))*(0 + 1)) denotes the language of binary strings with odd length.

P(x): if Sigma = {0, 1} and L_1 = { x \in Sigma x has odd length}, then L_1 = L(((0 + 1)(0 + 1))*(0 + 1)).
Claim: \forall x \in Sigma, P(x).
Proof:
(i) assume x \in Sigma and x \in L_1, then x has odd length, say x = 2*k + 1 for some k \in N. Then x can be written as a concatenation of some substrings of x, i.e. x = x_1x_2...x_kx_(k + 1), where
x_i for 1 <= i <= k carries 2 characters either 0 or 1 and 2*k characters in total;
x_(k + 1), the last character of x.
Since x_i \in L((0 + 1)(0 + 1)), x_1x_2...x_k \in L(((0 + 1)(0 + 1))^k), and x_(k + 1) \in L(0 + 1), x = x_1x_2...x_kx_(k + 1) \in L(((0 + 1)(0 + 1))^k)L(0 + 1) = L(((0 + 1)(0 + 1))^k(0 + 1)), which is a subset of L(((0 + 1)(0 + 1))*(0 + 1)). So L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)).
(ii) assume x \in Sigma and x is a typical string in the language denoted by L(((0 + 1)(0 + 1))*(0 + 1)). Then x can be written as a series of strings x_1x_2...x_k where each x_i carries 2 characters either 0 or 1 for some k \in N concatenated with a single character which can be either 0 or 1. Since each x_i has a length of 2, they have a length of 2*k in total. With the single character at the end, x = 2*k + 1 which is an odd number. So L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1.
Since L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)) and L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1, L_1 = L(((0 + 1)(0 + 1))*(0 + 1)) according to the set property.
Thus, \forall x \in Sigma, P(x).