Есть ли какие-то результаты по решению задач формальных языков с использованием математического анализа, непрерывной математики.
Например, решение проблемы непустоты пересечения для языка без контекста и обычного языка.
9
Есть ли какие-то результаты по решению задач формальных языков с использованием математического анализа, непрерывной математики.
Например, решение проблемы непустоты пересечения для языка без контекста и обычного языка.
Ответы:
Ламин прокомментировал связь с теоремой Хомского-Шютценбергера . В последнее время через эту связь было решено несколько исследовательских задач в теории формального языка с использованием непрерывной математики. Например:
Герман Грубер, Джонатан Ли и Джеффри Шаллит. Перечисление регулярных выражений и их языков . доступный онлайн на arxiv.org как arXiv: 1204.4982, 2012
Сабина Брода, Антонио Макиавело, Нельма Морейра, Роджерио Рейс: Руководство автостопщика по сложности описания с помощью аналитической комбинаторики . Теор. Вычи. Sci. 528: 85-100 (2014)
Сабина Брода, Антонио Макиавело, Нельма Морейра, Рожериу Рейс: Средний размер конструкций автоматов из регулярных выражений . Бюллетень EATCS 116 (2015)
Рафаэла Бастос, Сабина Брода, Антонио Макиавело, Нельма Морейра, Рожерио Рейс: О средней сложности автоматов с частичными производными для полурасширенных выражений . Журнал автоматов, языков и комбинаторики 22 (1-3): 5-28 (2017)
Первые две из вышеупомянутых ссылок также дают обзор математического и / или исторического фона.
источник
Одним из первых подключений является создание функций. Теорема Хомского-Шютценбергера утверждает, что производящая функция числа слов однозначной КЛЛ является алгебраической. В своей работе Flajolet доказывает, что некоторые КЛЛ по своей природе неоднозначны, показывая, что их порождающая функция трансцендентна (их «локальное поведение» вокруг их особенностей характерно для трансцендентных функций, например, логарифмические термины появляются в разложении).
В целом, вы должны смотреть на аналитической комбинаторики . Это дает прекрасную связь между формальными структурами и сложным анализом.
Флажолет, Филипп , Аналитические модели и неоднозначность контекстно-свободных языков , Теор. Вычи. Sci. 49, 283-309 (1987). ZBL0612.68069 .
источник
Работы Константина Васильевича Сафонова могут быть интересными. Например, «О разрешимости систем символьных полиномиальных уравнений» .
Системы некоммутативных полиномиальных уравнений, которые обсуждаются в данной работе, могут рассматриваться как грамматики, порождающие формальные языки. Например, контекстно-свободные языки. Это соотношение обсуждается во введении.
На эту тему есть еще работы Константина В. Сафонова, и некоторые из них более близки к теории формальных языков, но на русском языке. Например, ИНТЕГРАЛЬНОЕ ПРЕДСТАВЛЕНИЕ СИНТАКТИЧЕСКОГО ПОЛИНОМА .
Полный список публикаций вы можете найти здесь: http://www.mathnet.ru/rus/person37125
источник