An analogue of implicit mapping theorem to formal grammars.pdf Продолжая исследование, начатое в работах [1, 2], рассмотрим систему полиномиальных уравнений Pj(z, x) = 0, Pj(0, 0) = 0, j = 1,..., к, (1) которая решается относительно символов z = (zi,... , zn) в виде ФСР, зависящих от символов x = (xi,... , xm). Такие системы имеют приложения в теории формальных языков, поскольку являются грамматиками, порождающими важные классы формальных языков: контекстно-свободных, языков непосредственно составляющих, языков в нормальной форме Грейбах и др. [3, 4]. В теории формальных языков символы xi,... , xm называются терминальными и образуют словарь (алфавит) данного языка, а символы zi,... , zn называются нетерминальными и необходимы для задания грамматических правил. Над всеми символами определены некоммутативная операция умножения (конкатенации), коммутативная операция формальной суммы, а также коммутативная операция умножения на комплексные числа, поэтому можно рассматривать символьные многочлены и ФСР с числовыми (комплексными) коэффициентами. Наконец, мономы от терминальных символов интерпретируются как предложения языка, а каждый ФСР, который является решением системы (1), рассматривается как порождённый грамматикой формальный язык, т. е. формальная сумма всех «правильных» предложений этого языка [3, 4]. Исследовать решения символьных систем (1) достаточно трудно, поскольку некоммутативность умножения и отсутствие деления препятствуют исключению неизвестных, и поэтому в работах [1, 2] наряду с некоммутативной системой (1) рассмотрен её коммутативный образ, который получается в предположении, что все переменные, входящие в систему, принимают значения из поля комплексных чисел. Так, предположим, следуя [1], что все мономы от xi,... , xm занумерованы в лексикографическом порядке по возрастанию степеней в последовательность u0,u1,..., играющую роль базиса, тогда каждый ряд s можно единственным образом записать в виде разложения по этому базису с числовыми коэффициентами (s,Ui) при мономах щ: те s = Y, (s,Ui)ui. (2) i=0 Теперь поставим в соответствие ФСР (2) его коммутативный образ ci(s) -степенной ряд, который получается из s в предположении, что символы x1,... , xm (равно как и z1,... , zn) обозначают коммутативные переменные, принимающие значения из поля комплексных чисел [5]. В работе [1] рассмотрен коммутативный образ системы уравнений (1) ci(Pj(z,x)) = 0, j = 1,..., k, (3) и отмечено, что из совместности некоммутативной системы (1) следует совместность коммутативной системы (3), однако обратное утверждение неверно. Как результат, вопрос о достаточном условии совместности системы уравнений (1), важный для приложений, оставался открытым. Ниже дадим решение этого вопроса, получая достаточное условие совместности (и единственности решения) исходной некоммутативной системы (1) в терминах совместности коммутативной системы (3), которая легче поддаётся исследованию. Для этого рассмотрим систему уравнений (1) в случае, когда k = n. Пусть J(z,x) = det((ci(Pi(z,x)))z ) - якобиан системы уравнений (3) относительно переменных z1,... , zn. Дискретным (символьным) аналогом теоремы о неявном отображении является следующая теорема. Теорема 1. Если для некоммутативной символьной системы уравнений (1) выполнено неравенство J(0, 0) = 0, то она имеет единственное решение в виде ФСР. Замечание 1. Неравенство J(0,0) = 0 является условием теоремы о неявном отображении для коммутативной системы уравнений (3) с переменными в z1,... , и влечёт существование и единственность её голоморфного решения; тем не менее оказывается, что это неравенство влечёт также существование и единственность решения исходной некоммутативной символьной системы уравнений (1). Поскольку ФСР, которые являются компонентами решения системы (1), интерпретируются как формальные языки, порождённые грамматикой (1), то теорема 1 позволяет установить случаи, когда грамматика действительно определяет формальный язык. Заметим также, что решением системы (3) являются алгебраические функции, которые могут быть исследованы аналитическими методами [6-8].

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