# Is unary language with polynomial power context sensitive?

I suppose that $\Sigma = \{a\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language. Can I prove this with closure property of CSL for example like complement? Can any one help me to prove for instance $L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.

Not true for linear polynomials. E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar 'S --> aaaS | aa'. [unless you mean 'at most context-sensitive', not 'exactly context-sensitive']
Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b_km+c_k$ consecutive $a$s for some constants $b_k$, $c_k$ [think "Horner's Method"] and then 'cascades' to the next sub-grammar.
• That's not what context-sensitive means (at least not under the standard definition). Every context-free language is also a context-sensitive language. The standard definition says that $L$ is a context-sensitive language if there exists a context-sensitive grammar for $L$; there's no requirement that $L$ must be not-context-free. Perhaps you can adapt the 3rd paragraph to provide a proof of the claimed statement? I'm not quite clear about the details of what you're suggesting, though. How do you build such a sub-grammar? – D.W. Jan 30 '17 at 19:04
• A unary language $L$ is regular iff it is context-free iff the set $\{n : a^n \in L\}$ is eventually periodic. – Yuval Filmus Dec 27 '17 at 16:41