Episode of Proving the regular expression denotes a language.

Question. Consider the language L, consisting of strings over the alphabet /sigma = {0,1}; that have an even number of 1s. For each of the regular expressions below, either prove they denote L, or else nd a counter-example that shows they do not. Your counter-example should either exhibit a string that is inL but not denoted by the regular expression, or else one denoted by the regular expression that is not in L.

To give out a counter example is easy, so here I will not show that part.

(b) R2 = (0 + (10*1))*
R_2 does denote L.

UNDERSTANDING THE PROBLEM
To prove a regular expression denotes a language, we need to show that
R2 is a subset of L and L is a subset of R2. Here we can use structural
induction.

DEVISING A PLAN
1) Prove that R2 is a subset of L
2) Prove that L is a subset of R2

CARRYING OUT THE PLAN
Let L be the set of binary strings that have even number of 1s.
Then the regular expression R_2 = (0 + (10*1))* denotes L.
Claim: for any string x, x is in L if and only if x is in L(R_2)
1)
Proof.[IF] Let x be an arbitrary string in language L,
then x contains even number of 1s, say 2n for some natural number n.
Then x can be decomposed as the concatenation of X_1 through X_k
where X_i (1 <= i <= k) = substring with even number of 1s.
To have even 1s, and for small unit, X_i has either zero 1 or two 1s.
Then x can be formed as below:
x = (0 + (1(0...0)1))(0 + (1(0...0)1))......(0 + (1(0...0)1))
X_1 X_1 X_k
There might me one or more zeros between two 1s, thus we use (10*1)
to denote the substring with two 1s.
Then each X_i is in the language (0 + (10*1)), 1 <= i <= k.
So x is in the language L((0 + (10*1))^k) which is a subset of
L((0 + (10*1))*). Thus language L is a subset of L((0 + (10*1))*).

2)
[ONLY IF] Let x be an arbitrary string in L((0 + (10*1))*).
Then there is some natural number k, and y_0, y_1, ..., y_k in /sigma *
such that y_i is in L(0 + (10*1)), for all i such that 0 <= i <= k.
Therefore there are natural numbers m_1, m_2,...,m_k such that
y_i = 0 + 1(0^(m_i))1, for all i such that 0 <= i <= k.
Obviously, y_i is either 0 or 1(0^(m_i))1,
So y_i either has no 1 or two 1s.
Let a,b be two natural numbers where a + b = (k - 0 ) + 1 = k + 1.
Assume there are "a" substrings y_i that is 0, and "b" substrings
y_i that has two 1s. Then the total number of 1s is
0*a + 2*b = 2b, which is even. Thus x is in language L, as wanted.

Since every string in L(R_2) is in language L, and every string in
L is in L(R_2), R_2 denotes L.


Look Back
This episode can be used to prove most of the questions about
proving the regular expression R denotes L.