The range of non-linear natural polynomials cannot be context-free

01/12/2019

∙

by   Dömötör Pálvölgyi, et al.

∙

0

∙

share

Suppose that some polynomial f with rational coefficients takes only natural values at natural numbers, i.e., L={f(n)| n∈ N}⊂ N. We show that the base-k 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.