I need help to prove that the given CFG grammar $G$ is equivalent to language $L$:
as
$S\to 0S1 \mid SS \mid \varepsilon$
and
$L=\{w\in\{0,1\}^* \mid \#_0(w)=\#_1(w)\text{ and for any prefix } u \text{ of } w:\ \#_0(u)\ge\#_1(u)\}$
I need help only in proving: $L\subseteq L(G)$.
Thanks!
The inclusion $L \subseteq L(G)$ can be shown by (strong) induction on the length of $w \in L$.
Clearly any $0$-length string in $L$ can be generated by the given CFG.
Suppose for some $n > 0$ that every string in $L$ of length $<n$ can be generated by the CFG. Let $w$ be a string in $L$ of length $n$. Consider the least $k > 1$ such that the prefix of $w$ of length $k$ has as many $\mathtt{0}$s as $\mathtt{1}$s. (Note that $k \leq n$.)
If $k = n$, then $w = \mathtt{0} v \mathtt{1}$, where $v$ is a string of length $n-2$. By definition of $k$ one can show that $v \in L$.
As there are as many $\mathtt{0}$s as $\mathtt{1}$s in $w = \mathtt{0} v \mathtt{1}$, there are as many $\mathtt{0}$s as $\mathtt{1}$s in $v$.
If some prefix of $v$ has more $\mathtt{1}$s than $\mathtt{0}$s, then the shortest such prefix has exactly one more $\mathtt{1}$ than $\mathtt{0}$; call this prefix $v^\prime$. But then $\mathtt{0} v^\prime$ is a prefix of $w$ with as many $\mathtt{0}$s as $\mathtt{1}$s, contradicting our choice of $k$. Therefore every prefix of $v$ must has at least as many $\mathtt{0}$s as $\mathtt{1}$s.
By the induction hypothesis $v$ can be generated by the CFG, and by first invoking the rule $S \to \mathtt{0} S \mathtt{1}$ and then generating $v$ we can then generate $w$ from the CFG.
If $k < n$, then $w = \mathtt{0}v_0\mathtt{1}v_1$, where $v_0$ has length $k-2 < n$ and $v_1$ has length $<n$. By definition of $k$ one can show that $v_0, v_1 \in L$.
As there are as many $\mathtt{0}$s as $\mathtt{1}$s in $\mathtt{0}v_0\mathtt{1}$, there must be as many $\mathtt{0}$s as $\mathtt{1}$s in $v_0$.
(Using the same argument as above, every prefix of $v_0$ has at least as many $\mathtt{0}$s as $\mathtt{1}$s.)
As there are as many $\mathtt{0}$s as $\mathtt{1}$s in both $w = \mathtt{0}v_0\mathtt{1}v_1$ and $\mathtt{0}v_0\mathtt{1}$, there are as many $\mathtt{0}$s as $\mathtt{1}$s in $v_1$.
If $v_1^\prime$ is a prefix of $v_1$, then $\mathtt{0} v_0 \mathtt{1} v_1^\prime$ is a prefix of $w$, as so has at least as many $\mathtt{0}$s as $\mathtt{1}$s. As there are an equal number of $\mathtt{0}$s and $\mathtt{1}$s in $\mathtt{0} v_0 \mathtt{1}$, there must be at least as many $\mathtt{0}$s as $\mathtt{1}$s in $v_1^\prime$.
By the induction hypothesis both $v_0$ and $v_1$ can be generated by the CFG. We may then generate $w$ from the CFG by $$S \to SS \to \mathtt{0} S \mathtt{1} S \overbrace{\to \cdots \to \mathtt{0} v_0 \mathtt{1} S}^{\text{steps to generate }v_0} \; \overbrace{\to \cdots \to \mathtt{0} v_0 \mathtt{1} v_1}^{\text{steps to generate }v_1}$$