CFG - whose words contain exactly twice as many b's as a's. 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?
 A: 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.
A: It is easy to see that every word generated by your grammar have twice the number of $b$'s as $a$'s. It is also easy to check that any word generated by the following grammar, can also be generated by your grammar:
$S \to a S b S b \mid b S a S b \mid b S b S a \mid S S \mid \varepsilon$
A less simple to answer question is Why do these grammars always work?.
So take any word $x$ of length $n$ with twice as many $b$'s as $a$'s.
One may think of a graph/histogram, where the $x$ axis goes from $1$ to $n$, and on position $i$ we plot a bar of height "number of $a$'s minus half the number of $b$'s seen up to and including position $i$."
We now break the word at the points where the graph touches the $x$ axis (meaning it equals $0$); we will use the $S S$ production to get as many $S$'s as the number of parts we see in the graph. Let us show that each such part can be generated by a single $S$.
If the part starts with an $a$, it must end with a $b$ (otherwise the graph would have crossed the $x$ axis earlier). Then choose the first production $a S b S b$. The $b$ in the middle may be chosen to be the first index $i$ where the graph touches $1/2$. Note that it cannot reach $1/2$ via $-1/2$ with an $a$, without actually touching $0$ beforehand (since one must use $b$ to decrease, each $b$ giving a 1/2 decrement). So there must be a $b$ at that index. Hence the string after the first $a$ and before $i$ begins at and returns to $1$, i.e., it has twice the number of $b$'s as $a$'s; likewise for the string which begins after $i$ and ends before the last $b$; by induction hypothesis, both these strings can be generated by $S$.
A similar argument will work for the other two cases.
So this proof works, but it is long and tedious. Does anyone have a simpler argument?
