On the structure of the counting function of sparse context-free languages

We give an exact description of the counting function of a sparse context-free language. Let L be a sparse context-free language and let f(L) be its counting function. Then there exist polynomials p(0), P-1,..., Pk-1, with rational coefficients, and an integerconstant k(0), such that for any n >= k(0) one has f(L) (it) = p(j) (n) where j is such that j equivalent to n mod k. As a consequence one can easily show the decidability of some questions concerning sparse context-free languages. Finally, we show that for any sparse context-free language L there exists a regular language L' such that for any n >= 0 one has f(L) (n) = f(L') (it) and, therefore, f(L) is rational. (c) 2006 Elsevier B.V. All rights reserved.