Analytic models and ambiguity of context-free languages. (English) Zbl 0612.68069

We establish that several classical context-free languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour. To that purpose, we survey some general results on elementary analytic properties and enumerative uses of algebraic functions in relation to formal languages. In particular, the paper contains a general density theorem for unambiguous context-free languages.


68Q45 Formal languages and automata


Zbl 0571.68058
Full Text: DOI Link


[1] Autebert, J.-M.; Beauquier, J.; Boasson, L.; Nivat, M., Quelques problèmes ouverts en théorie des langages algébriques, RAIRO Inform. Théor., 13, 363-379 (1979) · Zbl 0434.68056
[2] Baron, G.; Kuich, W., The characterization of nonexpansive grammars by rational power series, Inform. and Control, 48, 109-118 (1981) · Zbl 0481.68075
[3] Beauquier, J.; Thimonier, L., Formal languages and Bernoulli processes, (LITP Rept. 83-30 (1983), Univ. Paris VII) · Zbl 0615.68055
[4] Ben-Or, M., Lower bounds for algebraic computation trees, Proc. 15th ACM Symp. on Theory of Computing, 80-86 (198)
[5] Berstel, J., Sur la densité asymptotique des langages formels, (Proc. 1st ICALP Colloquium (1972), North-Holland: North-Holland Amsterdam), 345-368
[6] Berstel, J., Contribution à l’étude des propriétés arithmétiques des langages formels, (Thèse (1972), Univ. Paris VII)
[7] Bertoni, A.; Sabadini, N., Algebricity of the generating function for context-free languages (1985), Manuscript
[8] Chandrasekharan, K., Arithmetical Functions (1970), Springer: Springer Berlin · Zbl 0217.31602
[9] Chomsky, N.; Schutzenberger, M.-P., The algebraic theory of context-free languages, (Computer Programming and Formal Systems (1963), North-Holland: North-Holland Amsterdam), 118-161 · Zbl 0148.00804
[10] Comtet, L., Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseignement Math., 10, 267-270 (1964) · Zbl 0166.41702
[11] Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[12] Crestin, J. P., Un langage non ambigu dont le carré est d’ambiguité inherente bornée, (Proc. 1st ICALP Colloquium (1972), North-Holland: North-Holland Amsterdam), 377-390 · Zbl 0277.68041
[13] Davies, B., Integral Transforms and Their Application (1978), Springer: Springer New York · Zbl 0381.44001
[14] Dieudonné, J., Calcul Infinitésimal (1968), Hermann: Hermann Paris · Zbl 0155.10001
[15] Feller, W., An Introduction to Probability Theory and its Application (1950), Wiley: Wiley New York · Zbl 0039.13201
[16] Flajolet, P.; Odlyzko, A., The expected height of binary trees and other simple trees, J. Comput. System Sci., 25, 171-213 (1982) · Zbl 0499.68027
[17] Flajolet, P.; Regnier, M.; Sedgewick, R., Some uses of the Mellin integral transform in the analysis of algorithms, (Combinatorics on Words (1985), Springer: Springer Berlin), 241-254
[18] Gelfond, A. O., Transcendental and Algebraic Numbers (1960), Dover: Dover New York · Zbl 0090.26103
[19] Guibas, L.; Odlyzko, A., Strings overlap, pattern-matching and non-transitive games, J. Comb. Theory. Ser. A, 30, 183-208 (1980) · Zbl 0454.68109
[20] Hardy, G. H., Ramanujan, Twelve Lectures Suggested by his Life and Work (1940), Cambridge, University Press: Cambridge, University Press London · Zbl 0025.10505
[21] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[22] Henrici, P., Applied and Computational Complex Analysis (1977), Wiley: Wiley New York · Zbl 0377.30002
[23] Hickey, T.; Cohen, J., Uniform random generation of strings in a context-free language, SIAM J. Comput., 12, 645-655 (1983) · Zbl 0524.68046
[24] Ibarra, O.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and transducer, (Proc. STACS’86. Proc. STACS’86, Lecture Notes in Computer Science, 210 (1986), Springer: Springer Berlin), 171-179
[25] Kemp, R., On the number of words in the language \({w ∈ Σ^∗¦w = w^R}^2\), Discrete Math., 40, 225-234 (1980) · Zbl 0485.68065
[26] Kemp, R., A note on the density of inherently ambiguous context-free languages, Acta Inform., 14, 295-298 (1980) · Zbl 0441.68085
[27] Kendig, K., Elementary Algebraic Geometry (1977), Springer: Springer New York · Zbl 0364.14001
[28] Knuth, D. E., The average time for carry propagation, Nederl. Akad. Wetensch. Indag. Math., 40, 238-242 (1978) · Zbl 0382.10035
[29] Kornai, A., Quantitative comparison of formal languages (1985), Manuscript, submitted
[30] Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer: Springer New York · Zbl 0582.68002
[31] Kuich, W.; Shyamasundar, R. K., The structure generating function of some families of languages, Inform. and Control, 32, 85-92 (1976) · Zbl 0338.68054
[32] Meir, A.; Moon, J., On the altitude of nodes in random trees, Canad. J. Math., 30, 997-1015 (1978) · Zbl 0394.05015
[33] Pippenger, N., Computational complexity in algebraic function fields, Proc. 20th IEEE Symp. FOCS, 61-65 (1979)
[34] Rudin, W., Real and Complex Analysis (1974), McGraw-Hill: McGraw-Hill New York
[35] Salomaa, A.; Soittola, M., Automata Theoretic Aspects of Formal Power Series (1978), Springer: Springer New York · Zbl 0377.68039
[36] Schneider, Th., Einfuehrung in die Transzendenten Zahlen (1957), Springer: Springer Berlin
[37] Seidenberg, A., Elements of the Theory of Algebraic Curves (1965), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0138.00301
[38] Shamir, E., Some inherently ambiguous context-free languages, Inform. and Control, 18, 355-363 (1971) · Zbl 0227.68039
[39] Shamos, M. I.; Yuval, G., Lower bounds from complex function theory, Proc. 17th IEEE Symp. FOCS, 268-273 (1976)
[40] Stanley, R., Differentiably finite power series, European J. Combin., 1, 175-188 (1980) · Zbl 0445.05012
[41] Whittaker, E. T.; Watson, G. N., A Course in Modern Analysis (1927), Cambridge University Press: Cambridge University Press London · Zbl 0108.26903
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.