<p>Lamine commented on the connection to the <a href="https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem" rel="noreferrer">Chomsky-Schützenberger enumeration theorem</a>. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:</p>

<ul>
<li><p>Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. <a href="http://arxiv.org/pdf/1204.4982" rel="noreferrer">Enumerating Regular Expressions and their Languages</a>. available online at arxiv.org as arXiv:1204.4982, 2012</p></li>
<li><p>Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
<a href="https://doi.org/10.1016/j.tcs.2014.02.013" rel="noreferrer">A Hitchhiker's Guide to descriptional complexity through analytic combinatorics</a>. Theor. Comput. Sci. 528: 85-100 (2014)</p></li>
<li><p>Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
<a href="http://eatcs.org/beatcs/index.php/beatcs/article/view/352" rel="noreferrer">Average Size of Automata Constructions from Regular Expressions</a>. Bulletin of the EATCS 116 (2015)</p></li>
<li><p>Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
<a href="https://www.jalc.de/issues/2017/issue_22_1-3/jalc-2017-005-028.php" rel="noreferrer">On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions</a>. Journal of Automata, Languages and Combinatorics 22(1-3): 5-28 (2017)</p></li>
</ul>

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

CC BY-SA 4.0
2019-01-20T21:06:53.213Z
2019-01-20T21:06:53.213Z
Hermann Gruber
<p>One of the first connections is via generating functions. The <a href="https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem" rel="noreferrer">Chomsky-Schützenberger</a> 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).</p>

<p>More generally, you should look at <a href="http://algo.inria.fr/flajolet/Publications/book.pdf" rel="noreferrer">Analytic combinatorics</a>. It gives a beautiful connection between formal structures and complex analysis.</p>

<p><em>Flajolet, Philippe</em>, <a href="http://dx.doi.org/10.1016/0304-3975(87)90011-9" rel="noreferrer"><strong>Analytic models and ambiguity of context-free languages</strong></a>, Theor. Comput. Sci. 49, 283-309 (1987). <a href="https://zbmath.org/?q=an:0612.68069" rel="noreferrer">ZBL0612.68069</a>.</p>

CC BY-SA 4.0
2019-01-21T08:27:24.083Z
2019-01-21T08:27:24.083Z
Lamine
<p>Works of Konstantin V. Safonov may be interesting. For example <a href="http://elib.sfu-kras.ru/bitstream/handle/2311/20240/egorushkin.pdf?sequence=4&amp;isAllowed=y" rel="nofollow noreferrer">"On Solvability of Systems of Symbolic Polynomial Equations"</a>.</p>

<p>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.</p>

<p>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 <a href="https://cyberleninka.ru/article/v/integralnoe-predstavlenie-sintaksicheskogo-mnogochlena" rel="nofollow noreferrer">AN INTEGRAL REPRESENTATION OF THE SYNTACTICAL POLYNOMIAL</a>. </p>

<p>A full list of publications you can found here: <a href="http://www.mathnet.ru/rus/person37125" rel="nofollow noreferrer">http://www.mathnet.ru/rus/person37125</a></p>

CC BY-SA 4.0
2019-01-14T14:24:05.377Z
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.
Sasho Nikolov
CC BY-SA 4.0
2019-01-14T12:10:56.920Z
2019-01-25T07:31:24.537Z
2019-01-25T07:31:24.537Z
gsv
<p>Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.</p>

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

CC BY-SA 4.0
2019-01-14T15:21:52.783Z
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.
Lamine
CC BY-SA 4.0
2019-01-20T21:07:40.103Z
@Lamine please consider converting your comment into an answer.
Hermann Gruber
<fl.formal-languages><automata-theory><context-free>
Continuous mathematics and formal language theory
Rustam
# Continuous mathematics and formal language theory

(Asked by: username_0 on 2019-01-14)

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.

**Tags:** fl.formal-languages, automata-theory, context-free

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1 please consider converting your comment into an answer.  

---

## 3 answers

### Answer by username_2 on 2019-01-20. Score: 7

username_1 commented on the connection to the [Chomsky-Schützenberger enumeration theorem](https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem). Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:

* username_2, Jonathan Lee, and Jeffrey Shallit. [Enumerating Regular Expressions and their Languages](http://arxiv.org/pdf/1204.4982). available online at arxiv.org as arXiv:1204.4982, 2012
* Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
  [A Hitchhiker's Guide to descriptional complexity through analytic combinatorics](https://doi.org/10.1016/j.tcs.2014.02.013). Theor. Comput. Sci. 528: 85-100 (2014)
* Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
  [Average Size of Automata Constructions from Regular Expressions](http://eatcs.org/beatcs/index.php/beatcs/article/view/352). Bulletin of the EATCS 116 (2015)
* Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
  [On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions](https://www.jalc.de/issues/2017/issue_22_1-3/jalc-2017-005-028.php). Journal of Automata, Languages and Combinatorics 22(1-3): 5-28 (2017)

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


---

### Answer by username_1 on 2019-01-21. Score: 6

One of the first connections is via generating functions. The [Chomsky-Schützenberger](https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem) 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](http://algo.inria.fr/flajolet/Publications/book.pdf). It gives a beautiful connection between formal structures and complex analysis.

*Flajolet, Philippe*, [**Analytic models and ambiguity of context-free languages**](http://dx.doi.org/10.1016/0304-3975(87)90011-9), Theor. Comput. Sci. 49, 283-309 (1987). [ZBL0612.68069](https://zbmath.org/?q=an:0612.68069).


---

### Answer by username_3 on 2019-01-14. Score: 3

Works of Konstantin V. Safonov may be interesting. For example ["On Solvability of Systems of Symbolic Polynomial Equations"](http://elib.sfu-kras.ru/bitstream/handle/2311/20240/egorushkin.pdf?sequence=4&isAllowed=y).

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](https://cyberleninka.ru/article/v/integralnoe-predstavlenie-sintaksicheskogo-mnogochlena).

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

> **Comments:**
> **username_4**: 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.  

---

