# Context-free grammar for ${a^n b^n a^n}$

I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can not find a context-free one. Any ideas?

• This language is not context free, so a context free grammar for it is impossible. It is a context sensitive language, however. Jan 31 '20 at 18:09

That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $$\{a\}$$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.
In particular, the language of all words like $$a^nb^na^n$$ is not context-free. The rough intuition to understand why it is not context-free is that a PDA cannot remember two unbounded independent relations. You can either use the pumping lemma to prove that fact.
• How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function? Feb 16 '20 at 4:01
How about $$\{a^{\Sigma(n)} \colon n \ge 1\}$$, where $$\Sigma$$ is Radó's noncomputablr busy-beaver function?