On the structure of the counting function of sparse context-free languages. (English) Zbl 1160.68407

Summary: 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,\dots,P_k-1\), with rational coefficients, and an integer constant \(k_0\), such that for any \(n\geq k_0\) one has \(f_L (n) = p_j (n)\) where \(j\) is such that \(j \equiv n \pmod 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\geq 0\) one has \(f_L (n) = f_L' (n)\) and, therefore, \(f_L\) is rational.


68Q45 Formal languages and automata
Full Text: DOI


[1] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[2] de Luca, A.; Varricchio, S., Finiteness and regularity in semigroups and formal languages, (1999), Springer Berlin · Zbl 0935.68056
[3] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. comput. sci., 49, 283-309, (1987) · Zbl 0612.68069
[4] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[5] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics: A foundation for computer science, (1989), Addison-Wesley Reading, MA · Zbl 0668.00003
[6] Honkala, J., Decision problems concerning thinness and slenderness of formal languages, Acta informatica, 35, 625-636, (1998) · Zbl 0909.68112
[7] Honkala, J., On Parikh slender context-free languages, Theoret. comput. sci., 255, 667-677, (2001) · Zbl 0974.68098
[8] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[9] O. Ibarra, B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers, Lecture Notes in Computer Science, Vol. 210, Springer, Berlin, 1986, pp. 171-179. · Zbl 0605.68080
[10] Ilie, L., On a conjecture about slender context-free languages, Theoret. comput. sci., 132, 427-434, (1994) · Zbl 0938.68707
[11] Ilie, L., On length of words in context-free languages, Theoret. comput. sci., 242, 327-359, (2000) · Zbl 0944.68099
[12] Ilie, L., On generalized slenderness of context-free languages, (), 189-202
[13] Ilie, L.; Rozenberg, G.; Salomaa, A., A characterization of poly-slender context-free languages, Theoret. inform. appl., 34, 77-86, (2000) · Zbl 0966.68097
[14] Incitti, R., The growth function of context-free languages, Theoret. comput. sci., 255, 601-605, (2001) · Zbl 0973.68117
[15] Latteux, M.; Thierrin, G., On bounded context-free languages, Elektron. informationsverarb. kybernet., 20, 3-8, (1984) · Zbl 0552.68062
[16] Raz, D., Length considerations in context-free languages, Theoret. comput. sci., 183, 21-32, (1997) · Zbl 0911.68097
[17] Sakarovitch, J., Éléments de théorie des automates, (2003), Vuibert Paris · Zbl 1178.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.