Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
contex-free languages; pumping lemma
contex-free languages; pumping lemma
Summary:
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.
References:
[1] Bar-Hillel, Y., Perles, M. A., Shamir, E.: 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 | MR 0151376
[2] Dömösi, P., Kudlek, M.: 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 | MR 1850234
[3] Ogden, W., Ross, R. J., Winklmann, K.: An “Interchange Lemma” for context-free languages. SIAM J. Comput. 14 (1982), 2, 410-415. DOI 10.1137/0214031 | MR 0784746
[4] Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, New York 2008. DOI 10.1017/cbo9780511808876
Search
Partner of
