What is the language of the given grammar?

Question

The given grammar goes as follows: $$S → aSa \mid B \mid \epsilon \\ Ba → bbBaa \\ aB → aaBbb \\ B → \epsilon$$ I derivated it and reached this language: $$L(G) = \{\epsilon, a^na^n, ab^2a^2, ab^4a^3, ab^6a^4, ab^8a^5, ..., a^nab^2a^2a^n, a^nab^4a^3a^n, ..., a^2b^3a, a^3b^6a, a^4b^9a, ..., a^na^2b^3aa^n, a^na^3b^6aa^n, a^na^4b^9aa^n, \} = \{a^nab^ma^oa^n : n \geq 0, m = 2k, o \geq 1\} \cup \{a^na^ob^maa^n : n \geq 0, m = 3k, o \geq 1\}$$ Is my resulted language correct?

Answer 1

This is a context-sensitive grammar. A typical expansion along these rules would proceed as follows.

First you use $S \to aSa$ a few times, then at some point you stop and turn $S$ to $B$, at this point having $a^n B a^n$ ($n \ge 0$). Then you either void $B$, or use one of the rules for $Ba$ or $aB$ unless $n=0$. If you expand $Ba$, you prevent yourself from expanding $aB$ afterwards, and vice versa. So the language seems to be $\{a^{2n}: n \ge 0\} \cup \{a^n b^{2k}a^{k+n}: n \ge 1, k \ge 1\} \cup \{a^{n+k} b^{2k} a^n: n \ge 1, k \ge 1\}$.