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

doi:10.17223/20710410/37/6

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О применении многомерного комплексного анализа в теории формальных языков и грамматик	672 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/37/6

#коммутативный образ

#синтаксический анализ

#интегральное представление

#формальный степенной ряд

Title: О применении многомерного комплексного анализа в теории формальных языков и грамматик
Title: On application of multidimensional complex analysis in formal language and grammar theory
Creator: Егорушкин, Олег Игоревич
|
Колбасина, Ирина Валерьевна
|
Сафонов, Константин Владимирович
Date: 2017
DOI: 10.17223/20710410/37/6
Description: Исследуются системы полиномиальных уравнений над полукольцом (относительно символов с некоммутативным умножением и коммутативным сложением). Такие системы уравнений интерпретируются как грамматики формальных языков и решаются относительно нетерминальных символов в виде формальных степенных рядов, зависящих от терминальных символов. Рассматривается коммутативный образ системы уравнений в предположении, что символы являются переменными, принимающими значения из поля комплексных чисел. Устанавливаются связи между решениями системы некоммутативных символьных уравнений и её коммутативного образа, тем самым методы многомерного комплексного анализа привлекаются в теорию формальных языков и грамматик. Доказывается дискретный аналог теоремы о неявном отображении для формальных грамматик: достаточным условием существования и единственности решения системы некоммутативных уравнений в виде формальных степенных рядов является отличие от нуля якобиана коммутативного образа этой системы. Предложен также новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического многочлена программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический многочлен монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа.