On a solution of polynomial grammars and the general algebraic equation.pdf Как известно, теория формальных языков имеет фундаментальное значение не только для лингвистики, но и программирования. Наиболее важные для приложений классы формальных грамматик можно записать в виде системы полиномиальных уравнений с некоммутативными переменными [1, 2]. Следуя [3, 4], понимаем под полиномиальной грамматикой систему полиномиальных уравнений Pj(z, x) = 0, Pj(0, 0) = 0, j = 1, . . . , k, которая решается относительно символов z = (zi, . . . , zn) в виде формальных степенных рядов, зависящих от символов x = (xi, . . . , xm). Символы xi,...,xm называются терминальными и образуют словарь языка, а символы zi,... , zn - нетерминальными, они необходимы для задания грамматических правил. Над всеми символами определена некоммутативная операция конкатенации и коммутативные операции формального сложения и умножения на числа, а значит, можно рассматривать ФСР с числовыми коэффициентами. Мономы от терминальных символов интерпретируются как предложения языка, а каждый ФСР - сумма всех «правильных» мономов, который является решением полиномиальной системы, понимается как порождённый грамматикой язык [1, 2]. Исследовать системы с некоммутативными символами очень трудно, и потому в работах [3 - 5] предложено рассмотреть коммутативный образ полиномиальной грамматики: для ФСР s коммутативный образ ci(s) получается в предположении, что все переменные коммутативны. Трудность исследования полиномиальных грамматик имеет место даже в случае одного уравнения: P1 (z, x) = 0. Так, известно [3, 4], что одно уравнение с некоммутативными неизвестными может: не иметь решений; иметь любое конечное число решений; иметь бесконечно много решений. Поэтому случай некоммутативных переменных принципиально отличается от уравнения над полем комплексных чисел, которое всегда разрешимо. Понятно, что достаточно рассмотреть общее алгебраическое уравнение Pl(z, x) = XnZn + Xn-iZn-1 + + Xiz + X0 = 0 (1) относительно символа z (здесь z = z1) и исследовать разложение неявной функции z = z(x), определяемой коммутативным образом уравнения (1) в степенной ряд либо ряд Лорана относительно переменных x0, x1, . . ., xn. С одной стороны, решение уравнения (1) представляет интерес для теории формальных языков и грамматик, с другой - конструктивное решение общего алгебраического уравнения в виде функции от коэффициентов является фундаментальной математической задачей, имеющей многовековую историю. Как известно, после открытия формул Кардано и Феррари для решения уравнений третьей и четвертой степени появилась некоторая надежда решать произвольное алгебраическое уравнение в радикалах, однако почти через триста лет, в 1826 г. , Абель доказал невозможность этого для уравнений пятой и более высоких степеней. Точнее, Абель доказал, что если существует формула, выражающая в радикалах корни уравнения пятой степени через его коэффициенты, то в случае действительных коэффициентов уравнение имеет либо один действительный корень, либо пять (очевидно, такое уравнение может иметь лишь три действительных корня, а значит, формулы в радикалах не существует). С этого времени конструктивное представление решений вызывает особый интерес. Конструктивное представление решения как функции от коэффициентов возможно в виде интегралов и рядов, что часто оказывается более удобным для приближённых вычислений. Так, в 1921 г. Меллин предложил решать общее уравнение с помощью гипергеометрических функций, причём разложение в ряд получено на основе интегрального представления Меллина - Барнса. В 1984 г. Умемура доказал разрешимость уравнения произвольной степени с помощью тэта-функций. В принципе, получить разложение в ряд неявной функции z = z(x1, . . ., xn), определяемой функциональным уравнением F(z, x1, . .., xn) = 0, не очень сложно. Как правило, такие разложения содержат оператор дифференцирования возрастающего порядка, либо коэффициенты степенного разложения даются формулой с возрастающим числом слагаемых. Теперь наша цель - найти конструктивный способ разложить в ряд неявную функцию z(x), заданную коммутативным образом уравнением (1), если возможно, в «замкнутом виде». Идея состоит в том, что функция z(x) -алгебраическая, и потому её ряд является диагональю ряда некоторой рациональной функции от переменных, число которых на 1 больше числа коэффициентов уравнения [6]. Рассмотрим произвольную ветвь z = z(x) решения уравнения (1), проходящую через точку (0, 0) (достаточно считать, что такая ветвь единственная). Теорема 1. Для функции, заданной коммутативным образом уравнения (1), имеет место разложение в ряд Лорана z(x) E (-1)k k2+...+kn>1 (2k2 + ... + nkn)! ((n - 1)kn + ... + k2 + 1)^!... kn! (n-1)kn+...+k2+1 0 -nkn- 1 ..-2k2-1 xk2 х2 kn . n. Поскольку в формуле решения степени переменной х1 отрицательные, то решение исходного некоммутативного уравнения (1) в виде ФСР невозможно, таким образом, имеет место следующее Следствие 1. Полиномиальная грамматика, порождённая уравнением (1), не имеет решения (не порождает полиномиального языка).

Скачать электронную версию публикации