How do you insure that from a CFG you get the same number of as and bs? I can make a CFG that makes sure we can produce any string that has the same number of as and bs, but I can't insure that those strings are the only ones that are produced. S => aS | bS | E The problem is that you can get something like this: aaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaabbb...bbbb. I don't think you can possibly cover all the cases.

$S \rightarrow aSbS | bSaS | \varepsilon$

it is obvious that this produces strings with the same number of $a$'s and $b$'s.

it is less obvious that this produces all of them :

Let $s$ be such a string. If its of the form $aSb$ or $bSa$ it's in the grammar described above.

If not, the first and last letter are the same (we assume it's $a$). Let $n$ be the length of the word, and $f(x)$ the number of a's minus the number of b's in the first $x$ letters of the word.

since $f(1)=1$, and $f(n-1)=-1$, then there exists a $x
* $f(x)=0$ (at this point same number of $a$'s and $b's$)
* $f(x-1)=1$ (the previous letter is a $b$)
* $f(x+1)=-1$ (the next letter is a $b$)



Therefore the word $s$ is of the form $aubbwa$ where the length of $aub$ is $x$. Since $f(x)=0$, $u$ contains the same number of $a$'s and $b's$, and therefore $bwa$ does too. Therefore $s$ is recognized by the above grammar.