How do you insure that from a CFG you get the same number of as and bs?

Question

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.

Answer 1

$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<n-1$ such that

• $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.