# Unrestricted grammar to generate $a^{n^2}$

I have been asked to find a grammar that will generate the language $\{a^{n^2}:n \ge0\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn't work. Any idea on how to setup such grammar? Any help will be appreciated.

## 2 Answers

Found the answer here. Basically the grammar looks like this: $$S→LAYR \\ ZA→aAZ \\ Za→aZ \\ ZR→AAYR \\ aY→Ya \\ AY→YA \\ LY→LZ \\ YR→X \\ aX→Xa \\ AX→Xa \\ LX→ε \\$$

• And what's the idea? Why would that be correct? – Raphael Mar 15 '17 at 21:53

Set aside $n$ of the $n^2$ characters, and use that $(n+1)^2 = n^2 + 2n +1$.

So at any moment we have (say) $n^2-n$ symbols $A$ and $n$ symbols $B$. We also need endmarkers. $L,R$ count as A$.$S\to LBBR$In one linear phase we visit all symbols, and each symbol$B$will generate two extra$A$'s. Finally we add a$B$.$L \to LX$;$XA\to AX$;$XB\to AABX$;$XR\to BR$Nondeterministically end, transforming all symbols into$a\$.

• This is a bit sketchy... – Yuval Filmus Mar 15 '17 at 19:12
• @YuvalFilmus OK. added details. – Hendrik Jan Mar 15 '17 at 21:21