Proving that everything in a language can be generated by a grammar

Question

Suppose $L=\{w \in {a,b}^* \colon \#b(w) = \#a(w) \}$, the language of all strings with an equal number of occurrences of $a$ and $b$ in all possible arrangements. Furthermore, this language can be generated by the grammar $G$ with rules:

$$S → aSbS\text{ }|\text{ }bSaS\text{ }|\text{ }ε$$

I realize that the standard approach is to prove (i) $L(G)\subseteq L$ and (ii) $L \subseteq L(G)$ by induction. How would one prove $L \subseteq L(G)$ by induction given that the string $w$ can contain an equal number of $a$ and $b$ characters in any arrangement?

Answer 1

Hint:

• Take any word $w \in L$ and split it $w = w_1w_2$ such that $w_1$ is the shortest non-empty prefix of $w$ that also belongs to $L$ (it might happen that $w_1 = w$).
• $w_2$ is strictly shorter than $w$ so you can use the inductive hypothesis.
• $w_1$ has to start with $a$ or $b$ and end with $b$ or $a$ respectively, so you can strip these letters and get a strictly shorter word $w_1'$ which also belongs to $L$.

I hope this helps $\ddot\smile$