# Given CFG generates all words with equally many 0s and 1s

Here is an exercise from an introduction to computation class:

Show that the following context-free grammar $$G$$ generates the language $$L$$ of words over $$\{0,1\}$$ with an equal number of $$0$$s and $$1$$s: $$S \to \epsilon \mid SS \mid 0S1 \mid 1S0$$

How should I prove that $$L⊆ L(G)$$ and $$L(G) ⊆ L$$?

I think I should start with the difference of 0's and 1's but have no clue where to start.

One direction is easy. To prove that $$L(G) \subseteq L$$, we prove by induction on the length of the derivation that every word generated by $$G$$ has an equal number of 0s and 1s. This amounts to proving the following statements:
• $$\epsilon \in L$$.
• If $$x,y \in L$$ then $$xy \in L$$.
• If $$x \in L$$ then $$0x1,1x0 \in L$$.
The other direction, proving that $$L \subseteq L(G)$$, is more challenging. We have to show that every word in $$L$$ is generated by $$L(G)$$. The proof is by induction on the length of the word. The base case, which is the empty word, is easy. Now consider any non-empty words $$w = \sigma_1 \ldots \sigma_n \in L$$. Let $$\delta(i) = \#_1(\sigma_1 \ldots \sigma_i) - \#_0(\sigma_1 \ldots \sigma_i)$$. The sequence $$\delta(0), \ldots, \delta(n)$$ starts and ends with $$0$$, and each element differs from the preceding one by $$\pm 1$$. Suppose that $$\delta(1) = 1$$, hence $$\sigma_1 = 1$$. Let $$i$$ be the minimal index $$i > 0$$ such that $$\delta(i) = 0$$ (such an index exists since $$\delta(n) = 0$$). Then $$\delta(i-1) = 1$$, hence $$\sigma_i = 0$$. You can check that $$x = w_2 \ldots w_{i-1}$$ and $$y = w_{i+1} \ldots w_n$$ are both in $$L$$. By induction, $$S \Rightarrow^* x,y$$. Therefore $$S \Rightarrow SS \Rightarrow 1S0S \Rightarrow^* 0x1y = w.$$ If $$\delta(1) = -1$$ then instead we use the rule $$S \Rightarrow 0S1$$.