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.
9
Odpowiedzi:
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.
źródło
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 .
źródło
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
źródło