Mathématiques continues et théorie du langage formel

9

S'il y a des résultats sur la résolution des problèmes de langage formel en utilisant l'analyse mathématique, les mathématiques continues.

Par exemple, résoudre le problème de non-vacuité d'intersection pour une langue sans contexte et une langue régulière.

fl.formal-languages automata-theory context-free Rustam
la source
1
Pour moi, le meilleur exemple est le merveilleux article de Flajolet: Flajolet, P. (1987). Modèles analytiques et ambiguïté des langages sans contexte. Informatique théorique, 49 (2-3), 283-309. La plupart des travaux de Flajolet portent sur le lien entre l'analyse (complexe), les langages formels et la combinatoire. Vous pouvez trouver beaucoup plus d'exemples dans son livre avec Sedgewick.
Lamine le
1
@Lamine, pensez à convertir votre commentaire en réponse.
Hermann Gruber

Réponses:

6

Lamine a commenté le lien avec le théorème d'énumération de Chomsky-Schützenberger . Récemment, quelques problèmes de recherche en théorie du langage formel ont été résolus en utilisant les mathématiques continues via cette connexion. Par exemple:

Les deux premières références ci-dessus donnent également un aperçu du contexte mathématique et / ou historique.

Hermann Gruber
la source
5

L'une des premières connexions se fait via des fonctions de génération. Le théorème de Chomsky-Schützenberger affirme que la fonction génératrice du nombre de mots d'un CFL non ambigu est algébrique. Dans son article, Flajolet prouve que plusieurs LFC sont intrinsèquement ambiguës en montrant que leur fonction génératrice est transcendantale (leur «comportement local» autour de leurs singularités est caractéristique des fonctions transcendantales, par exemple, des termes logarithmiques apparaissent dans l'expansion).

Plus généralement, vous devriez regarder la combinatoire analytique . Il donne une belle connexion entre les structures formelles et l'analyse complexe.

Flajolet, Philippe , Modèles analytiques et ambiguïté des langages sans contexte , Théor. Comput. Sci. 49, 283-309 (1987). ZBL0612.68069 .

Lamine
la source
2

Les travaux de Konstantin V. Safonov peuvent être intéressants. Par exemple, "Sur la solvabilité des systèmes d'équations polynomiales symboliques" .

Les systèmes d'équations polynomiales non commutatives qui sont discutés dans ce travail peuvent être traités comme des grammaires qui génèrent des langages formels. Par exemple, des langues sans contexte. Cette relation est discutée dans l'introduction.

Il y a plus d'ouvrages de Konstantin V. Safonov sur ce sujet, et certains d'entre eux sont plus fermés à la théorie des langues formelles, mais ils sont en russe. Par exemple UNE REPRÉSENTATION INTÉGRALE DU POLYNOMIAL SYNTACTIQUE .

Une liste complète des publications que vous pouvez trouver ici: http://www.mathnet.ru/rus/person37125

gsv
la source
Je ne pense pas que cela réponde à la question. L'article lié concerne un problème algébrique. Je n'y vois aucun lien intéressant avec l'analyse.
Sasho Nikolov