CFG - whose words contain exactly twice as many b's as a's.

Question

I am trying to built a CFG for the language that accepts all words that have twice as many b's as a's. The only idea I could come up with is:

Start -> S

S-> SaSbSbS | SbSaSbS | SbSbSaS | $\epsilon$

But obviously it will not be able to parse the word aaabbbbbb Because it doesn't matter what combination I pick, there will still be an S which can not be parsed further as it will contain either only a's or b's (if I am wrong please guide me how do I parse this word using the above CFG).

The worst part is that googling brought either the same solution or something similar although written is some other manner, but still unable to parse the above word.

The question is: is there a CFG for the language that accepts twice as many b's as a's (being able to parse the given word) and if yes, what is it?

Answer 1

You’re forgetting the $\epsilon$-productions. Your grammar does generate $aaabbbbbb$:

$$S\Rightarrow SaSbSbS\Rightarrow^* aSbb\Rightarrow aSaSbSbSbb\Rightarrow^* aaSbbbb\Rightarrow^* aaabbbbbb\;.$$

The first and second $\Rightarrow^*$ use $S\to\epsilon$ three times each; the last abbreviates a longer sequence of applications of productions, but at that point it should be clear what they are.