Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i.\,e., $L=\{f(n)\mid n\in {\mathbb N}\}\subseteq {\mathbb N}$. We show that the base-$q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
contex-free languages, pumping lemma
68Q45