|
ПДМ, 2017, номер 37, страницы 76–89
(Mi pdm590)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математические основы информатики и программирования
О применении многомерного комплексного анализа в теории формальных языков и грамматик
О. И. Егорушкин, И. В. Колбасина, К. В. Сафонов Сибирский государственный университет науки и технологий им. акад. М. Ф. Решетнёва, г. Красноярск, Россия
Аннотация:
Исследуются системы полиномиальных уравнений над полукольцом (относительно символов с некоммутативным умножением и коммутативным сложением). Такие системы уравнений интерпретируются как грамматики формальных языков и решаются относительно нетерминальных символов в виде формальных степенных рядов, зависящих от терминальных символов. Рассматривается коммутативный образ системы уравнений в предположении, что символы являются переменными, принимающими значения из поля комплексных чисел. Устанавливаются связи между решениями системы некоммутативных символьных уравнений и её коммутативного образа, тем самым методы многомерного комплексного анализа привлекаются в теорию формальных языков и грамматик. Доказывается дискретный аналог теоремы о неявном отображении для формальных грамматик: достаточным условием существования и единственности решения системы некоммутативных уравнений в виде формальных степенных рядов является отличие от нуля якобиана коммутативного образа этой системы. Предложен также новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического многочлена программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический многочлен монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа.
Ключевые слова:
формальный степенной ряд, коммутативный образ, синтаксический анализ, интегральное представление.
Финансовая поддержка |
Номер гранта |
Российский фонд фундаментальных исследований  |
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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Р. В. Ульверт, “О вычислимости кратных интегралов суммой локальных вычетов”, Сиб. электрон. матем. изв., 15 (2018), 996–1010
[R. V. Ul'vert, “On Computability of Multiple Integrals By Means of a Sum of Local Residues”, Sib. Electron. Math. Rep., 15 (2018), 996–1010 ]
|
Просмотров: |
Эта страница: | 228 | Полный текст: | 92 | Литература: | 25 |
|