Matemática continua y teoría del lenguaje formal.

9

Si hay algunos resultados en la resolución de problemas de idiomas formales utilizando análisis matemáticos, matemáticas continuas.

Por ejemplo, resolver el problema de la intersección del no vacío para un lenguaje libre de contexto y un lenguaje regular.

Rustam
fuente
1
Para mí, el mejor ejemplo es el maravilloso artículo de Flajolet: Flajolet, P. (1987). Modelos analíticos y ambigüedad de lenguajes libres de contexto. Informática teórica, 49 (2-3), 283-309. La mayor parte del trabajo de Flajolet trata sobre la conexión entre análisis (complejos), lenguajes formales y combinatoria. Puedes encontrar muchos más ejemplos en su libro con Sedgewick.
Lamine
1
@Lamine, por favor considere convertir su comentario en una respuesta.
Hermann Gruber el

Respuestas:

6

Lamine comentó sobre la conexión con el teorema de enumeración de Chomsky-Schützenberger . Recientemente, algunos problemas de investigación en la teoría del lenguaje formal se resolvieron usando matemáticas continuas a través de esta conexión. Por ejemplo:

Las dos primeras de las referencias anteriores también dan una encuesta de los antecedentes matemáticos y / o históricos.

Hermann Gruber
fuente
5

Una de las primeras conexiones es mediante funciones generadoras. El teorema de Chomsky-Schützenberger establece que la función generadora del número de palabras de un CFL inequívoco es algebraica. En su artículo, Flajolet demuestra que varios CFL son intrínsecamente ambiguos al demostrar que su función generadora es trascendental (su "comportamiento local" en torno a sus singularidades es característico de las funciones trascendentales, por ejemplo, los términos logarítmicos aparecen en la expansión).

En términos más generales, debería mirar Combinatoria analítica . Da una hermosa conexión entre las estructuras formales y el análisis complejo.

Flajolet, Philippe , Modelos analíticos y ambigüedad de lenguajes libres de contexto , Theor. Comput Sci. 49, 283-309 (1987). ZBL0612.68069 .

Lamina
fuente
2

Las obras de Konstantin V. Safonov pueden ser interesantes. Por ejemplo, "Sobre la solubilidad de los sistemas de ecuaciones polinómicas simbólicas" .

Los sistemas de ecuaciones polinómicas no conmutativas que se analizan en este trabajo pueden tratarse como gramáticas que generan lenguajes formales. Por ejemplo, lenguajes sin contexto. Esta relación se discute en la Introducción.

Hay más trabajos de Konstantin V. Safonov sobre este tema, y ​​algunos de ellos están más cerrados a la teoría de los idiomas formales, pero están en ruso. Por ejemplo, una representación integral del polinomio sintáctico .

Puede encontrar una lista completa de publicaciones aquí: http://www.mathnet.ru/rus/person37125

gsv
fuente
No creo que responda la pregunta. El artículo vinculado trata sobre un problema algebraico. No veo ninguna conexión interesante con el análisis allí.
Sasho Nikolov