Kybernetika 56 no. 4, 722-726, 2020

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

Dömötör PálvölgyiDOI: 10.14736/kyb-2020-4-0722

Abstract:

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.

Keywords:

contex-free languages, pumping lemma

Classification:

68Q45

References:

  1. Y. Bar-Hillel, M. A. Perles and E. Shamir: On formal properties of simple phrase-structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14 (1961), 2, 143-172.   DOI:10.1524/stuf.1961.14.14.143
  2. P. Dömösi and M. Kudlek: Strong iteration lemmata for regular, linear, context-free, and linear indexed languages. In: Fund. Comput. Theory 1999, pp. 226-233.   DOI:10.1007/3-540-48321-7\_18
  3. W. Ogden, R. J. Ross and K. Winklmann: An "Interchange Lemma'' for context-free languages. SIAM J. Comput. 14 (1982), 2, 410-415.   DOI:10.1137/0214031
  4. J. Shallit: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, New York 2008.   DOI:10.1017/cbo9780511808876