Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.

For example, solving the intersection non-emptiness problem for a context-free language and a regular language.

  • 1
    $\begingroup$ For me the best example is the wonderful paper by Flajolet : Flajolet, P. (1987). Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49(2-3), 283-309. Most of Flajolet's work is about the connection between (complex) analysis , formal languages and combinatorics. You can find much more examples in his book with Sedgewick. $\endgroup$ – Lamine Jan 14 at 15:21
  • 1
    $\begingroup$ @Lamine please consider converting your comment into an answer. $\endgroup$ – Hermann Gruber Jan 20 at 21:07

Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:

The first two of the above references also give a survey of the mathematical and/or historical background.


One of the first connections is via generating functions. The Chomsky-Schützenberger theorem states that the generating function of the number of words of a unambiguous CFL is algebraic. In his paper, Flajolet proves that several CFL are inherently ambiguous by showing that their generating function is transcendental (their “local behavior” around their singularities is characteristic of transcendental functions, for example, logarithmic terms appear in the expansion).

More generally, you should look at Analytic combinatorics. It gives a beautiful connection between formal structures and complex analysis.

Flajolet, Philippe, Analytic models and ambiguity of context-free languages, Theor. Comput. Sci. 49, 283-309 (1987). ZBL0612.68069.


Works of Konstantin V. Safonov may be interesting. For example "On Solvability of Systems of Symbolic Polynomial Equations".

Systems of non-commutative polynomial equations which are discussed in this work may be treated as grammars that generate formal languages. For example, context-free languages. This relation is discussed in the Introduction.

There are more works of Konstantin V. Safonov on this topic, and some of them are more closed to formal languages theory, but they are in Russian. For example AN INTEGRAL REPRESENTATION OF THE SYNTACTICAL POLYNOMIAL.

A full list of publications you can found here: http://www.mathnet.ru/rus/person37125

  • 4
    $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$ – Gamow Jan 14 at 12:37
  • $\begingroup$ I don’t think it answers the question. The paper linked is about an algebraic problem. I don’t see any interesting connection with analysis there. $\endgroup$ – Sasho Nikolov Jan 14 at 14:24
  • $\begingroup$ @Gamow thanks for comments. Fixed. $\endgroup$ – gsv Jan 25 at 7:35
  • $\begingroup$ @SashoNikolov thanks for comments. Fixed. $\endgroup$ – gsv Jan 25 at 7:35

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.