How to design a Context-Free Grammar and Pushdown Automaton for the following language

Question

How would you design a context-free grammar for the following language? $$ L = \{a^{(n^3+1)}\mid n \geq 1\} $$ And derive a Pushdown Automaton that accepts the same language. Any help given would be greatly appreciated as I am completely lost and struggling to get the answer.

Answer 1

Your language isn't context-free.

It is well-known that a unary language (a subset of $a^*$ for some letter $a$) is context-free iff it is regular iff the set $\{ n : a^n \in L \}$ is eventually periodic. You can check in any number of ways that $\{n^3+1 : n \geq 1\}$ isn't eventually periodic (for example, it has zero density yet isn't finite), and so the language is neither regular nor context-free.