# CF grammar on this language

I'm trying to write a context-free grammar for this language:

$L = \{a^n b a^m (bb)^n : m \ge 1, n \ge 0\}$

I was getting lost with maintaining $n$ number of $a$'s and $(bb)$'s and I'm not sure how to fix it. The terminals don't seem to be working out because I think splitting it up between lines is just asking for the $n$ to not be the same between the 2 terminals that require it (as I stated above). The $m$ seems ok though:

$S \rightarrow a S b b \mid A$

$A \rightarrow b B$

$B \rightarrow a B \mid a$

Would be very helpful if someone can get me back on track.

-

## 1 Answer

It looks fine: there’s nothing there to be fixed. Any derivation must look like this:

$$S\Rightarrow^n a^nSb^{2n}\Rightarrow a^nb^{2n}\Rightarrow a^nbBb^{2n}\Rightarrow^m a^nba^mBb^{2n}\Rightarrow a^nba^{m+1}b^{2n}\;,$$

where $n$ is the number of times you use $S\to aSbb$, and $m$ is the number of times you use $B\to aB$. Since $n,m\ge 0$, this gives you exactly what you want.

-
Great thanks, it didn't feel like I was including everything but yes you showed me how I was. +1 and accepted. –  stackuser Nov 3 '13 at 15:52
@stackuser: You’re welcome. (What I did there is a useful technique if your grammar doesn’t do much branching.) –  Brian M. Scott Nov 3 '13 at 16:02