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

Описание

Перевод названия: On application of multidimensional complex analysis in formal language and grammar theory

Тип публикации: статья из журнала

Год издания: 2017

Идентификатор DOI: 10.17223/20710410/37/6

Ключевые слова: формальный степенной ряд, коммутативный образ, синтаксический анализ, интегральное представление, Formal power series, commutative image, syntactic analysis, integral representation

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

Ссылки на полный текст

Издание

Журнал: Прикладная дискретная математика

Выпуск журнала: 37

Номера страниц: 76-89

ISSN журнала: 20710410

Место издания: Томск

Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет"

Авторы

  • Егорушкин Олег Игоревич (Сибирский государственный университет науки и технологий им. акад. М. Ф. Решетнёва)
  • Колбасина Ирина Валерьевна (Сибирский государственный университет науки и технологий им. акад. М. Ф. Решетнёва)
  • Сафонов Константин Владимирович (Сибирский государственный университет науки и технологий им. акад. М. Ф. Решетнёва)

Вхождение в базы данных

  • РИНЦ (eLIBRARY.RU) (цитирований 1)
  • Ядро РИНЦ (eLIBRARY.RU)
  • Список ВАК
  • Web of Science Core Collection
  • Scopus