Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.
1 Answer
A unary language (a subset of $a^*$) is context-free iff it is regular. This is a special case of Parikh's theorem. It is not too hard to show that a unary language $L$ is regular if and only if there exist $n,m$ such that for all $N \geq n$, $a^N \in L$ iff $a^{N+m} \in L$. See if this condition holds for your language.