Se existem resultados na resolução de problemas de linguagens formais usando análise matemática, matemática contínua.
Por exemplo, resolvendo o problema de não vazio de interseção para uma linguagem livre de contexto e uma linguagem regular.
9
Respostas:
Lamine comentou a conexão com o teorema da enumeração de Chomsky-Schützenberger . Recentemente, alguns problemas de pesquisa na teoria formal da linguagem foram resolvidos usando a matemática contínua por essa conexão. Por exemplo:
Hermann Gruber, Jonathan Lee e Jeffrey Shallit. Enumerando expressões regulares e seus idiomas . disponível online em arxiv.org como arXiv: 1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: Guia do Mochileiro para a complexidade descritiva através da combinatória analítica . Theor. Comput. Sci. 528: 85-100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: tamanho médio das construções de autómatos a partir de expressões regulares . Boletim do EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: Sobre a complexidade média dos autômatos derivativos parciais para expressões semi-estendidas . Journal of Automata, Languages and Combinatorics 22 (1-3): 5-28 (2017)
As duas primeiras referências acima também fornecem um levantamento do contexto matemático e / ou histórico.
fonte
Uma das primeiras conexões é através da geração de funções. O teorema de Chomsky-Schützenberger afirma que a função geradora do número de palavras de uma CFL inequívoca é algébrica. Em seu artigo, Flajolet prova que várias CFL são inerentemente ambíguas, mostrando que sua função geradora é transcendental (seu "comportamento local" em torno de suas singularidades é característico das funções transcendentais, por exemplo, termos logarítmicos aparecem na expansão).
De maneira mais geral, você deve analisar a combinatória analítica . Ele fornece uma bela conexão entre estruturas formais e análises complexas.
Flajolet, Philippe , Modelos analíticos e ambiguidade de linguagens livres de contexto , Theor. Comput. Sci. 49, 283-309 (1987). ZBL0612.68069 .
fonte
Os trabalhos de Konstantin V. Safonov podem ser interessantes. Por exemplo "Sobre a solvabilidade de sistemas de equações polinomiais simbólicas" .
Os sistemas de equações polinomiais não comutativas discutidos neste trabalho podem ser tratados como gramáticas que geram linguagens formais. Por exemplo, linguagens sem contexto. Essa relação é discutida na introdução.
Existem mais trabalhos de Konstantin V. Safonov sobre esse assunto, e alguns deles estão mais fechados à teoria das línguas formais, mas estão em russo. Por exemplo, UMA REPRESENTAÇÃO INTEGRAL DO POLINOMIAL SINTÁTICO .
Uma lista completa de publicações que você pode encontrar aqui: http://www.mathnet.ru/rus/person37125
fonte