Developing a Context Free Grammar whilst knowing the number of terminals

Question

I am trying to develop a CFG for the language $L$ defined by:

$L = \{a^{n+2}bba^{n-2} | n > 1\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

$S \rightarrow aaaaXbbX$ (Production 1)

$X \rightarrow aX | \Lambda $ (Production 2)

This would be right if we were somehow forced to substitute the same value of the non-terminal $X$ in both its appearances in production 1. However, we can substitute $X \rightarrow aX$ in its first apperance in production 1 and $X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $a's$ off as defined in the language $L$.

The first question is, is there even a CFG for this?

Well, I would say according to theory, yes there is because:

• I am asked to draw a Determinate Push Down Automata for this language; and
• According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?

Answer 1

Your attempt was pretty close! But I think that this is the way to go for you

$$S \rightarrow a a a a X$$

$$X \rightarrow a X a \mid b b$$

The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.

So after that, it's a question of making a CFG that generates $L = \{a^n b b a^n \mid n \geq 0\}$. That's exactly what $X$ does. Every time you see a $X$ you have to put a leading and trailing $a$ in and you can't terminate until you put the $b b$ in the middle since otherwise the $X$ gets expanded to another $X$.