# Context free grammar problem for number of a's is twice the number of b's

Can you to find for me a context free grammar for the following language?

$$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\}$$

Here $$\#_a(w)$$ counts the number of $$a$$'s in $$w$$.

Let $$c(w)=2\#_b(w)-\#_a(w)$$. Your language is exactly $$\{w\mid c(w)=0\}$$.

Now consider a string $$w$$ with $$c(w)=0$$ and $$|w|\ge 2$$. If we can split $$w$$ into three parts: $$w=pms$$ such that $$c(p)$$ and $$c(pm)$$ have different signs, i.e., $$c(p)c(pm)<0$$, then there are two cases:

1. $$c(p)>0$$ and $$c(pm)<0$$. Note each time we append a character to string $$x$$, $$c(x)$$ is either increased by 2 or decreased by 1, so we can always split $$m$$ into two parts $$m_1m_2$$ such that $$c(pm_1)=0$$.

2. $$c(p)<0$$ and $$c(pm)>0$$. In this case we can always split $$m$$ into two parts $$m_1m_2$$ such that either $$c(pm_1)=0$$, or $$c(pm_1)=-1$$ and $$m_2$$ begins with $$b$$.

As a result, either $$w=w_1w_2$$ where $$c(w_1)=c(w_2)=0$$, or $$w=w_1bw_2$$ where $$c(w_1)=c(w_2)=-1$$.

If $$w$$ cannot be split into such three parts, then $$w$$ must be either $$bw_1aa$$ or $$aaw_1b$$ where $$c(w_1)=0$$.

So, if we let $$S_-$$ generate the language of strings where $$2\#_b-\#_a=-1$$, then we have the following grammar \begin{align} S&\rightarrow SS\mid S_-bS_-\mid bSaa\mid aaSb\mid\epsilon\\ S_-&\rightarrow aS\mid SS_- \end{align}

• Is the obtained grammar unambiguous? If yes, how can we prove it? May 1, 2021 at 23:22

The following grammar generates the language $$L = \{ w \in \{a, b\}^*\ | \ \#_a(w) = 2\#_b(w) \}$$.

S -> bSaa | baSa |
aSba | abSa |
aSab | aaSb |
SS | ε


First, for every b introduced, 2 a's are introduced. The location of an b could be before, between, or after both a's.

Aside for the rule S -> SS, the grammar generates the string from outside in. Thus, there is no left or right recursion. So there are two places in each rule where recursion could happen: inside on the left and inside on the right.

Suppose there is a string $$w = bxb \in L$$. An example of such a string would be baaaab. Since $$\#_a(w) = 2\#_b(w)$$, then $$\#_a(x) = 2(\#_b(x) + 2)$$. There must exists at least one point in $$x$$ such that $$x = x_1x_2$$ where $$bx_1 \in L$$ and $$x_2b \in L$$. Hence the rule S -> SS.

Edit: The following rules must be added. See the accepted answer for a complete solution. These rules allows us to build string from inside out.

S -> QbQ
Q -> aS | SQ

• No, it doesn't. It generates the language $L = \{a^ib^{2i}\mid i\ge 0\}$.
– rici
Aug 5, 2020 at 23:04
• I've edited my solution. First a misunderstanding between $\#_a(w) = 2\#_b(w)$ and $2\#_a(w) = \#_b(w)$ and an oversight of where symbols can be located (i.e. it's not necessary for all a's to be followed by all b's). Aug 6, 2020 at 1:22
• Your grammar seems not to generate $aaabbbaaa$. Aug 6, 2020 at 10:34