Ciągła matematyka i formalna teoria języka

9

Czy istnieją jakieś wyniki w rozwiązywaniu problemów języków formalnych za pomocą analizy matematycznej, matematyki ciągłej.

Na przykład rozwiązanie problemu braku pustki na skrzyżowaniu dla języka bezkontekstowego i języka zwykłego.

fl.formal-languages automata-theory context-free

— Rustam
źródło

1

Dla mnie najlepszym przykładem jest wspaniały artykuł Flajolet: Flajolet, P. (1987). Modele analityczne i niejednoznaczność języków bezkontekstowych. Informatyka teoretyczna, 49 (2-3), 283–309. Większość prac Flajoleta dotyczy związku między (złożoną) analizą, językami formalnymi i kombinatoryką. Możesz znaleźć znacznie więcej przykładów w jego książce z Sedgewick.

— Lamine

1

@ Lamin, proszę rozważyć przekształcenie komentarza w odpowiedź.

— Hermann Gruber,

6

Lamine skomentował związek z twierdzeniem wyliczenia Chomsky'ego-Schützenbergera . Ostatnio rozwiązano kilka problemów badawczych w formalnej teorii języka za pomocą ciągłej matematyki za pośrednictwem tego połączenia. Na przykład:

Hermann Gruber, Jonathan Lee i Jeffrey Shallit. Wyliczanie wyrażeń regularnych i ich języków . dostępny online na arxiv.org jako arXiv: 1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: Przewodnik autostopowicza o złożoności opisowej poprzez kombinatorykę analityczną . Teoria Comput. Sci. 528: 85–100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: Średnia wielkość konstrukcji automatów z wyrażeń regularnych . Biuletyn EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: O średniej złożoności częściowych pochodnych automatów dla wyrażeń częściowo rozszerzonych . Journal of Automata, Languages and Combinatorics 22 (1-3): 5-28 (2017)

Dwa pierwsze z powyższych odniesień zawierają również przegląd tła matematycznego i / lub historycznego.

— Hermann Gruber
źródło

5

Jednym z pierwszych połączeń jest generowanie funkcji. Twierdzenie Chomsky'ego-Schützenbergera stwierdza, że funkcja generująca liczbę słów jednoznacznego CFL jest algebraiczna. W swojej pracy Flajolet udowadnia, że kilka CFL jest z natury niejednoznacznych, pokazując, że ich funkcja generująca jest transcendentalna (ich „lokalne zachowanie” wokół ich osobliwości jest charakterystyczne dla funkcji transcendentalnych, na przykład w rozwinięciu pojawiają się terminy logarytmiczne).

Mówiąc bardziej ogólnie, powinieneś spojrzeć na kombinatorykę analityczną . Daje piękny związek między strukturami formalnymi a złożoną analizą.

Flajolet, Philippe , modele analityczne i dwuznaczność języków bezkontekstowych , Teoria. Comput. Sci. 49, 283–309 (1987). ZBL0612.68069 .

— Lamine
źródło

2

Ciekawe mogą być prace Konstantina V. Safonowa. Na przykład „O rozwiązalności układów symbolicznych równań wielomianowych” .

Układy nieprzemiennych równań wielomianowych omówione w tej pracy można traktować jako gramatyki generujące języki formalne. Na przykład języki bezkontekstowe. Relację tę omówiono we wstępie.

Jest więcej prac Konstantina V. Safonowa na ten temat, a niektóre z nich są bardziej zamknięte na teorię języków formalnych, ale są w języku rosyjskim. Na przykład INTEGRALNA REPREZENTACJA SYNTACTICAL POLYNOMIAL .

Pełna lista publikacji znajduje się tutaj: http://www.mathnet.ru/rus/person37125

— gsv
źródło

Nie sądzę, że to odpowiada na pytanie. Powiązany dokument dotyczy problemu algebraicznego. Nie widzę tam żadnego interesującego związku z analizą.

— Sasho Nikolov