# How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

For language $$L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick example, for string $$x = aabb$$ we have these derivations: $$S \rightarrow aSbS \rightarrow^* aaSbSb\varepsilon \rightarrow^* aa\varepsilon b \varepsilon b \rightarrow aabb$$). Then I was asked to provide a mathematical proof, which is more like to be intended as a formalism, to prove, indeed, the correctness of such CFG.

Arguably, by induction, one could assume it holds that $$\forall k\leq n$$, $$|x| = 2k$$ and then test a string $$x$$ with number of characters $$|x| = 2n + 2$$. So string $$x$$ is in the form of $$x = au'bu''$$. But now how can I show that $$u'$$ and $$u''$$ still contain an equal number of $$a$$'s and $$b$$'s? Sorry if I'm missing something and might be easier than I think.

There are two implications involved in the correctness. Every string in $$L$$ can be derived by the CFG (completeness) and every string derived by the grammar belongs to $$L$$ (consistency). I think you want an argument to formalize the first implication by induction.
Assuming the string $$x\in L$$ starts with an $$a$$, there must be a position with letter $$b$$ such that the string is of the form $$aubv$$ such that the $$\#_a(u)=\#_b(u)$$. The argument I know is by counting. Read the letters in $$x$$ one by one, and add $$1$$ for each $$a$$, subtract $$1$$ for each $$b$$. As the number of $$a$$'s equals the number of $$b$$'s, the count starts and stops with $$0$$. The counts becomes $$1$$ after the first letter, and must drop back to $$0$$ at some position with a $$b$$. In between we have seen an equal number of $$a$$'s and $$b$$'s.
Now that $$x=aubv$$ with $$x\in L$$ and $$u\in L$$ it is easy to argue that also $$v\in L$$.
• Good reasoning, and as regards the consistency property, i.e. $L(G) \subseteq L$, it is basically already proved because, being $S \rightarrow aSbS \mid bSaS$, we can reach $x = aubu$ or $x = buau$ at a certain point, and $x \in L$, right? – Antonio Frighetto Oct 26 '18 at 11:37
• @Antonio Indeed, $L(G)\subseteq L$ is easy by design of the grammar. If $S\Rightarrow^* u$ and $S\Rightarrow^* v$ assuming $u,v\in L$, then also $aubv, buav\in L$. Induction on the length of the derivation, or depth of the derivation tree. – Hendrik Jan Oct 26 '18 at 14:12