О применении многомерного комплексного анализа в теории формальных языков и грамматик О. И. Егорушкин, И. В. Колбасина, К. В. Сафонов
Material type: ArticleOther title: On application of multidimensional complex analysis in formal language and grammar theory [Parallel title]Subject(s): коммутативный образ | синтаксический анализ | интегральное представление | формальный степенной рядGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 37. С. 76-89Abstract: Исследуются системы полиномиальных уравнений над полукольцом (относительно символов с некоммутативным умножением и коммутативным сложением). Такие системы уравнений интерпретируются как грамматики формальных языков и решаются относительно нетерминальных символов в виде формальных степенных рядов, зависящих от терминальных символов. Рассматривается коммутативный образ системы уравнений в предположении, что символы являются переменными, принимающими значения из поля комплексных чисел. Устанавливаются связи между решениями системы некоммутативных символьных уравнений и её коммутативного образа, тем самым методы многомерного комплексного анализа привлекаются в теорию формальных языков и грамматик. Доказывается дискретный аналог теоремы о неявном отображении для формальных грамматик: достаточным условием существования и единственности решения системы некоммутативных уравнений в виде формальных степенных рядов является отличие от нуля якобиана коммутативного образа этой системы. Предложен также новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического многочлена программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический многочлен монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа.Библиогр.: 13 назв.
Исследуются системы полиномиальных уравнений над полукольцом (относительно символов с некоммутативным умножением и коммутативным сложением). Такие системы уравнений интерпретируются как грамматики формальных языков и решаются относительно нетерминальных символов в виде формальных степенных рядов, зависящих от терминальных символов. Рассматривается коммутативный образ системы уравнений в предположении, что символы являются переменными, принимающими значения из поля комплексных чисел. Устанавливаются связи между решениями системы некоммутативных символьных уравнений и её коммутативного образа, тем самым методы многомерного комплексного анализа привлекаются в теорию формальных языков и грамматик. Доказывается дискретный аналог теоремы о неявном отображении для формальных грамматик: достаточным условием существования и единственности решения системы некоммутативных уравнений в виде формальных степенных рядов является отличие от нуля якобиана коммутативного образа этой системы. Предложен также новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического многочлена программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический многочлен монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа.
There are no comments on this title.