Create a context-free grammar

Question

Is $L = \{a^nb^2a^n \mid n \geq 0\}$ a context-free language?

And if so, would the following language be context-free? $\begin{align}\{S &\to aSa \\ S &\to b\}\end{align}$

I think it is context-free because the pumping lemma for determining if it is a regular language doesn't hold, but I'm not sure.

This question comes from a Natural Language Processing exercise, not sure about the origin.

Answer 1

The language $L$ is context-free but the grammar you specified does not produce this language. The second rule should be modified to be $S \to bb$.

Now to prove that your language is context-free, you must show that you have a context-free-grammar that produces exactly this language.

Note however, that the pumping-lemma can only be used to show that a certain language is not regular. $L$ is not regular by the pumping-lemma, but this doesn't tell you anything about whether $L$ is context-free.