8
$\begingroup$

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.

$\endgroup$
  • 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 yesterday
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Do you mean something like this?

$\endgroup$
  • 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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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