RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2017, номер 37, страницы 76–89 (Mi pdm590)  

Математические основы информатики и программирования

О применении многомерного комплексного анализа в теории формальных языков и грамматик

О. И. Егорушкин, И. В. Колбасина, К. В. Сафонов

Сибирский государственный университет науки и технологий им. акад. М. Ф. Решетнёва, г. Красноярск, Россия

Аннотация: Исследуются системы полиномиальных уравнений над полукольцом (относительно символов с некоммутативным умножением и коммутативным сложением). Такие системы уравнений интерпретируются как грамматики формальных языков и решаются относительно нетерминальных символов в виде формальных степенных рядов, зависящих от терминальных символов. Рассматривается коммутативный образ системы уравнений в предположении, что символы являются переменными, принимающими значения из поля комплексных чисел. Устанавливаются связи между решениями системы некоммутативных символьных уравнений и её коммутативного образа, тем самым методы многомерного комплексного анализа привлекаются в теорию формальных языков и грамматик. Доказывается дискретный аналог теоремы о неявном отображении для формальных грамматик: достаточным условием существования и единственности решения системы некоммутативных уравнений в виде формальных степенных рядов является отличие от нуля якобиана коммутативного образа этой системы. Предложен также новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического многочлена программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический многочлен монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа.

Ключевые слова: формальный степенной ряд, коммутативный образ, синтаксический анализ, интегральное представление.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-47-240318
Исследование выполнено при финансовой поддержке РФФИ и Правительства Красноярского края в рамках научного проекта № 17-47-240318.


DOI: https://doi.org/10.17223/20710410/37/6

Полный текст: PDF файл (702 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.682

Образец цитирования: О. И. Егорушкин, И. В. Колбасина, К. В. Сафонов, “О применении многомерного комплексного анализа в теории формальных языков и грамматик”, ПДМ, 2017, № 37, 76–89

Цитирование в формате AMSBIB
\RBibitem{EgoKolSaf17}
\by О.~И.~Егорушкин, И.~В.~Колбасина, К.~В.~Сафонов
\paper О применении многомерного комплексного анализа в~теории формальных языков и грамматик
\jour ПДМ
\yr 2017
\issue 37
\pages 76--89
\mathnet{http://mi.mathnet.ru/pdm590}
\crossref{https://doi.org/10.17223/20710410/37/6}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm590
  • http://mi.mathnet.ru/rus/pdm/y2017/i3/p76

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:179
    Полный текст:74
    Литература:21

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019