Геометрическое условие разрешимости формальных грамматик | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/31

Геометрическое условие разрешимости формальных грамматик

В работе продолжено развитие метода исследований формальных грамматик, под которыми подразумеваются системы некоммутативных полиномиальных уравнений. Такие системы решаются в виде формальных степенных рядов (ФСР), которые выражают нетерминальные символы алфавита через терминальные; первая компонента решения является формальным языком. Метод, развиваемый авторами, основывается на изучении коммутативного образа грамматики и формального языка, а именно: всякому ФСР поставлен в соответствие его коммутативный образ, который получается, если считать, что все символы являются коммутативными переменными. Получена теорема, которая даёт достаточное геометрическое условие того, что формальная грамматика имеет единственное решение в виде ФСР.

Geometric condition of formal grammars solvability.pdf Как известно, теория формальных языков имеет фундаментальное значение не только для лингвистики, но и программирования. На ней базируются поиск в интернете, машинный перевод текстов, речевой диалог с компьютером, развитие языка математических абстракций, распознавание генетического кода в биоинформатике, обнаружение кода мигрирующих вирусов, разработка и реализация языков программирования, оптимизация компиляторов, перенос разработанных компьютерных программ в новую вычислительную среду и другие современные технологии. Все эти приложения используют взаимосвязи языка (как множества возможных текстов) с грамматикой (сводом формальных правил, определяющих языковые конструкции и их равнозначимость). Более того, всюду нужны быстрые качественные алгоритмы формальных построений грамматики по языку и языка по грамматике и синтаксического анализа конструкций, немыслимые без серьёзного теоретического обоснования. Контекстно-свободные грамматики, наряду с регулярными выражениями, активно используются для решения задач, связанных с разработкой формальных языков и синтаксических анализаторов [1-3]. Одним из основных достоинств контекстно-свободных грамматик является возможность задания широкого класса языков при сохранении относительной компактности представления [4, 5]. С уровнем контекстно-свободных языков соотносится атрибутивная модель процесса, определяющая описание моделируемого процесса в виде моделей бизнес-процессов. Переход к контекстно-свободным языкам выполняется за счёт моделирования бизнес-процесса с применением инструментов структурного или объектно-ориентированного подхода. Бизнес-процесс, представленный в форме структурной или объектной модели, использует алфавит и синтаксис конкретного языка моделирования, что позволяет описывать процесс независимо от предметной области [6]. Следуя обозначениям [1, 2], рассмотрим систему полиномиальных уравнений P3 (z,x) = 0, P3(0, 0) = 0, j = 1,..., k, (1) которая решается относительно символов z = (zi,...,zn) в виде формальных степенных рядов, зависящих от символов x = (xi,... , xm). Системы такого вида имеют приложения в теории формальных языков, поскольку обобщают важные классы грамматик [3, 4]. Символы xi,...,xm называются терминальными и образуют словарь языка, а символы zi,... , zn - нетерминальными, они необходимы для задания грамматических правил. Над всеми символами определена некоммутативная операция конкатенации и коммутативная операция формальной суммы, а также коммутативная операция умножения на числа, и потому можно рассматривать ФСР с числовыми коэффициентами. Мономы от терминальных символов интерпретируются как предложения языка, а каждый ФСР (сумма всех «правильных» мономов), который является решением системы (1), понимается как порождённый грамматикой формальный язык [3, 4]. Поскольку исследовать системы с некоммутативными символами трудно, в [1, 2] предложено рассмотреть коммутативный образ системы (1), который получается в предположении, что все переменные коммутативны; обозначим коммутативный образ ФСР s через ci(s) [5]. В работе [1] рассмотрен коммутативный образ ci(Pj(z,x)) = 0, j = 1,..., k, (2) системы уравнений (1) и отмечено, что из совместности некоммутативной системы (1) следует совместность коммутативной системы (2), а обратное утверждение неверно. Поэтому вопрос о достаточном условии совместности системы (1) остаётся открытым, частично его решает применение такого инструмента, как якобиан. Пусть k = n; J(z,x) = det((ci(Pi(z,x)))Zj) -якобиан системы уравнений (2) по переменным zi,..., zn. Ранее была доказана следующая Теорема 1 [1]. Если для некоммутативной символьной системы уравнений (1) выполнено неравенство J(0, 0) = 0, то она имеет единственное решение в виде ФСР. Естественно, она неприменима, когда якобиан J(0, 0) равен нулю, однако обойти эту ситуацию в ряде случаев помогают геометрические соображения. Имеет место следующий результат: Теорема 2. Если для некоммутативной символьной системы уравнений (1) множества {ci(Pj (z, 0)) = 0} в n-мерном комплексном пространстве являются гладкими комплексными аналитическими поверхностями в точке 0, j = 1,... , n, а нормали к ним, проведённые из этой точки, линейно независимы, то система (1) имеет единственное решение в виде ФСР. Таким образом, теорема 2, обобщая теорему 1, позволяет установить, когда грамматика действительно порождает формальный язык. При этом компонентами решения системы (2) являются алгебраические функции, которые могут быть исследованы аналитически [6-8].

Ключевые слова

системы полиномиальных уравнений, некоммутативные переменные, формальный степенной ряд, коммутативный образ, аналитичекая гиперповерхность, systems of polynomial equations, non-commutative variables, formal power series, commutative image, analytic hypersurface

Авторы

ФИООрганизацияДополнительноE-mail
Егорушкин Олег ИгоревичСибирский государственный университет науки и технологий имени академика М. Ф. Решетнёвакандидат физико-математических наук, доцентolegegoruschkin@yandex.ru
Колбасина Ирина ВалерьевнаСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёваассистентkabaskina@yandex.ru
Сафонов Константин ВладимировичСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёвадоктор физико-математических наук, профессор, заведующий кафедройsafonovkv@rambler.ru
Всего: 3

Ссылки

Егорушкин О. И., Колбасина И. В., Сафонов К. В. О совместности систем символьных полиномиальных уравнений и их приложении // Прикладная дискретная математика. Приложение. 2016. №9. С. 119-121.
Egorushkin O. I., Kolbasina I. V., and Safonov K. V. On solvability of systems of symbolic polynomial equations // Журн. СФУ. Сер. Матем. и физ. 2016. Т. 9. Вып. 2. С. 166-172.
Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1973.
Salomaa A. and Soitolla M. Automata-Theoretic Aspects of Formal Power Series. N.Y.: Springer Verlag, 1978.
Семёнов А. Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик // Доклады АН СССР. 1973. №212. С. 50-52.
Сафонов К. В., Егорушкин О. И. О синтаксическом анализе и проблеме В. М. Глушкова распознавания контекстно-свободных языков Хомского // Вестник Томского госуниверситета. 2006. Приложение №17. С. 63-67.
Сафонов К. В. Об условиях алгебраичности и рациональности суммы степенного ряда // Матем. заметки. 1987. Т. 41. Вып.3. С. 325-332.
Safonov K. V. On power series of algebraic and rational functions in Cn // J. Math. Analysis Appl. 2000. V. 243. P. 261-277.
 Геометрическое условие разрешимости формальных грамматик | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/31

Геометрическое условие разрешимости формальных грамматик | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/31