# Is my grammar correct for this context-free language?

$\{a^nb^2a^n \mid n \ge0\}$

I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between.

I came up with the following grammar, but I think it accepts strings that it should not such as: $abb, bba$, etc.

\begin{align} S&\rightarrow X\\ X&\rightarrow XbbX \mid \epsilon\\ A&\rightarrow aA \mid \epsilon \end{align}

• Your grammar doesn't generate any word with an $a$ in it. – David Richerby May 11 '14 at 7:37

In dealing with CFGs, it's often useful to work from the inside out. Clearly $$S\rightarrow aSa$$ will generate all strings of the form $a^nSa^n$, for $n\ge 0$. Then all you have to do is allow the possibility that $S$ will also eventually generate $bb$, which we can do by the production $S\rightarrow bb$, giving the grammar $$S\rightarrow aSa\mid bb$$ or, if you wanted to be explicit about the $bb$ central part, you could write \begin{align} S&\rightarrow aSa \mid T\\ T&\rightarrow bb \end{align} The problem with your grammar is that it can't guarantee that there will be the same number of $a$s on each end of a generated string.