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 fL be its counting function. Then there exist polynomials p0,p1,…,pk-1, with rational coefficients, and an integer constant k0, such that for any n⩾k0 one has fL(n)=pj(n) where j is such that . 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 fL(n)=fL′(n) and, therefore, fL is rational.