Does there exist context-free grammar with words of length n^2 or n^3?

Question

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to substitute each $S$ with sequence of $S$'s of length $n$.

Answer 1

For a language $L$, let $N(L) = \{|w| : w \in L\}$, and let $U(L) = \{1^n : n \in N(L)\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\{1^{n^2} : n \geq 0 \}$ is not regular, no context-free language $L$ satisfies $N(L) = \{n^2 : n \geq 0\}$. In fact, no infinite context-free language $L$ even satisfies $N(L) \subseteq \{n^2 : n \geq 0\}$ (exercise).

Answer 2

Yuval's answer uses Parikh's theorem to show that if L is context-free then U(L) is regular, and then (implicitly) the pumping lemma for regular languages to show that U(L) is not regular.

The use of Parikh's theorem can be avoided using the pumping lemma for context-free languages.

If $L$ is infinite and context-free, then there is a word $uvwxy$ with $|vx|>0$ such that $uv^kwx^ky \in L$ for all $k \ge 0$. So, $|uwy|+k|vx| \in N(L)$ for all $k$. Since $|vx| \ge 0$, this is an infinite arithmetic progression. In general, if $L$ is infinite, then $N(L)$ contains an infinite arithmetic progression (this is weaker than what we get from Parikh's theorem, which gives us that $N(L)$ is entirely made up of a finite union of arithmetic progressions).

The set $\{n^c : n\ge 0\}$ contains no infinite arithmetic progression when $c>1$. Note that the gap between $n^c$ and $(n+1)^c$ grows to infinity, so at some point it must be larger than any given $b$, so if $a+kb= n^c$, then $n^c < a+(k+1)b < (n+1)^c$ for large enough $n$, so $\{a+kb :k\ge0\} \not\subseteq \{n^c:n\ge 0\}$.