Polya's problem

This was taken out of the CFG problems section of the textbook.

Problem : Prove that the following CDF generates the set of strings over {0.1} that have equally many 0s and 1s.
S -> 0S1S
S -> 1S0S
s -> E

1. Understanding the Problem:
We need to prove that the CDF gives a string with equal number of 1s and 0s.

2. Devise a Plan:
I'll probably have to use three cases, one for 0S1S, 1S0S and E. I'll also need to use induction (simple)

3. Carrying out the plan:
Base Case: If S -> E, then there are no 0s or 1s. That means that there are equal numbers of 1s and 0s.
Inductive Step: Assume that S is of equal number of 1s and 0s by IH.
Case 1S0S: Let the string be 1S0S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
Case 0S1S: Let the string be 0S1S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
By all cases listed above, this CDF produces the same number of 1s and 0s.

4. Looking Back:
I think this result makes sense. There lacks a structure, but the logic is still retained.