Context free grammar for the same amount of a’s and b’s, with the b’s in the middle

Question

I need to convert the following language to a CFG $$ L = \{\ a^n b^{n+k} a^k \in \{a,b\}^* \ |\ n \ge 0\ ,\ k\ge 0 \} \ . $$ So far I have: $$ \begin{aligned} S &\Rightarrow SASBSA \ ,\\ A &\Rightarrow a\ ,\\ B &\Rightarrow bb|b\ . \end{aligned} $$ But I don't think this is correct. It's not quite a palindrome as $n$ and $k$ can be odd. I'm struggling with the $n+k$ part.

Answer 1

Since we can have $a^nb^n$ and $b^na^n$ we can generate our strings by multiplying a prefix $P$ by a suffix $Q$. Let $S$ be our start symbol. $$S\to\epsilon$$ $$S\to P$$ $$S\to Q$$ $$S\to PQ$$ $$P\to aPb$$ $$Q\to bQa$$ $$P\to ab$$ $$Q\to ba$$