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, 2019 at 15:21
  • 1
    $\begingroup$ @Lamine please consider converting your comment into an answer. $\endgroup$ Jan 20, 2019 at 21:07

3 Answers 3


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

  • $\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$ Jan 14, 2019 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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