Find CFG for language $\#_a(w) = 2\#_b(w)$

Question

$L=\{w\in (a+b)^*:\#_a(w) = 2\#_b(w)\}$
I can think grammar:
$S\rightarrow abSa\ |\ aaSb\ |\ baSa\ |\ bSaa\ |\ aSba\ |\ aSab\ |\ SS$
But I couldn't prove that it is full (generates all words). When it comes to corectness: Induction with length. But what about fullness ? Could you show how to prove it ?

Answer 1

The empty word is in $L$, so you need to add $S\to\lambda$; I’ll assume that this has been done. It turns out that your grammar doesn’t generate all of $L$, even after this minor correction is made. Rather than simply show you an example of a word in $L$ that is not generated by your grammar, I’ll attempt to prove that your grammar does generate $L$ and see where I get stuck. I’ll use a technique that can be quite useful when a language is defined in terms of a simple relationship amongst the numbers of instances of the various characters.

Say that a word $w\in L$ is atomic if no proper initial segment of $w$ is in $L$. Let $w=x_1\ldots x_{3n}$ be any word in $\{a,b\}^*$ whose length is a multiple of $3$. Let $s_0=0$, and recursively define $s_k$ for $k=1,\ldots,3n$ by letting

$$s_k=\begin{cases} s_{k-1}+1,&\text{if }x_k=a\\ s_{k-1}-2,&\text{if }x_k=b\;. \end{cases}$$

• Show that $w\in L$ if and only if $s_{3n}=0$.
• Show that $w$ is atomic if and only if $s_{3n}=0$, and $s_k\ne 0$ for $k\in\{1,\ldots,3n-1\}$.

Because of the production $S\to SS$, it suffices to show that each atomic member of $L$ is generated by $S$. Suppose not; then there is a shortest atomic $w\in L$ that is not generated by $S$. Clearly $|w|$ is a positive multiple of $3$, so $w=x_1\ldots x_{3n}$ for some $n\in\Bbb Z^+$.

• Show that if $w$ has any of the forms $abua$, $aaub$, $baua$, $buaa$, $auba$, or $auab$, then $u$ is an atomic word in $L$ that is not generated by $S$, contradicting the minimality of $w$.

• Conclude that $w$ has one of the forms $aauaa$, $abubb$, $bbuba$, or $bub$.

• If $u=bub$, then $s_1=-2$ and $s_{3n-1}=2$. (Why?) Show that there must be a $k$ between $1$ and $3n-1$ such that $s_k=0$, and conclude that $w$ is not atomic after all.

• Make a similar argument if $w=abubb$ or $w=bbuba$.

This leaves only the case $w=aauaa$. In this case $s_2=2$ and $s_{3n-2}=-2$, but the downsteps in $s_k$ are of size $2$, so it’s possible to step from $s_k=1$ to $s_{k+1}=-1$ without hitting $0$. This means that the argument that I hope you found for the other three cases won’t work here. And in fact a little experimentation shows that $aaabbbaaa$ is in $L$ (and is even atomic) but is not generated by your grammar.

This argument shows that your grammar generates every atomic word of $L$ that does not have the form $aauaa$. Note that if $u$ starts or ends with $b$, $w$ is not atomic, so you’re really missing only the atomic members of $L$ of the form $aaauaaa$.

Suppose that $w=aua\in L$; clearly $s_1=1$, and $s_{3n-1}=-1$.

• Show that either $s_k=0$ for some $k$ between $1$ and $3n-1$, in which case $w$ is not atomic, or there is a $k$ such that $1\le k\le 3n-2$, $s_k=1$, and $s_{k+1}=-1$, so that $x_{k+1}=b$. Show that in this case $u=vby$, where $v,y\in L$.

Use this to show that adding $S\to aSbSa$ will complete your grammar.