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

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$.

• Yes, for instance the finite language {aaaa, aaab, aaaaaaaaa, aaaaaaaab} contains words of length $2^2$ and $3^2$. – immibis Jun 27 '16 at 0:44
• Please edit the question to clarify what you're asking. I can see multiple ways to parse what you've written. Do you mean that every word in the language must have a length that is a perfect square or perfect cube? That at least one word must have such a length? Must the language be infinite? Do you want a single language where lengths are squares or cubes, or are you asking if there's a language whose lengths are squares or a language whose lengths are cubes? Or something else entirely? – David Richerby Jun 27 '16 at 12:09

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).
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\}$.