Polynomial grammars generating an infinite set of languages.pdf Как известно, теория формальных языков имеет фундаментальное значение как для лингвистики, так и программирования. Многочисленные приложения используют взаимосвязи языка (как множества возможных текстов) с грамматикой (сводом формальных правил, определяющих языковые конструкции и их равнозначимость). В этой связи нужны быстрые качественные алгоритмы формальных построений грамматики по языку и языка по грамматике, а также синтаксического анализа конструкций, что невозможно без серьёзного теоретического обоснования. Рассмотрим систему полиномиальных уравнений Pj(z, x) = 0, Pj(0, 0) = 0, j = 1, . .., n, (1) которая решается относительно символов z = (z1, . . ., zn) в виде формальных степенных рядов (ФСР), зависящих от символов x = (x1, . .., xm). Системы такого вида обобщают важные классы формальных грамматик [1, 2] и называются полиномиальными грамматиками [3, 4]. Одним из достоинств полиномиальных, в частности контекстно-свободных, грамматик является возможность задания широкого класса языков при сохранении относительной компактности представления [1-4]. Символы xi,... ,xm называются терминальными, они образуют словарь языка, а символы z1,... , zn - нетерминальными, они необходимы для задания грамматических правил. Над всеми символами определена некоммутативная операция конкатенации и коммутативная операция формальной суммы, а также коммутативная операция умножения на числа, что позволяет рассматривать ФСР с числовыми коэффициентами. Мономы от терминальных символов рассматриваются как предложения языка, а каждый ФСР (сумма всех «правильных» мономов) - компонент решения системы (1) понимается как порождённый грамматикой язык [1, 2]. Для полиномиальных грамматик актуальны вопросы существования, единственности и бесконечности решений, причём для понимания последней ситуации необходимо сделать уточнения. Дадим следующее Определение 1. Будем говорить, что полиномиальная грамматика (1) имеет бесконечно много решений (порождает бесконечное множество языков), если множество решений системы (1) зависит хотя бы от одного произвольного ФСР от символов x1 , . . . , xm . Так, система из двух одинаковых уравнений x1z1 - z2x2 = 0 имеет тождественно равный нулю якобиан и бесконечно много решений, поскольку решения можно записать в виде z1 = sx2, z2 = x1s, где s - произвольный ФСР от x1, x2. Поскольку исследовать системы с некоммутативными символами трудно, в работах [3-5] предложено использовать коммутативный образ системы (1), который получается, если считать все переменные коммутативными. Обозначая коммутативный образ ФСР s через ci(s), рассмотрим коммутативный образ ci(Pj(z, x)) = 0, j = 1, . . . , n, (2) системы уравнений (1). Отметим, что из совместности некоммутативной системы (1) следует совместность коммутативной системы (2), а обратное утверждение неверно, что подчёркивает актуальность вопросов, связанных с совместностью системы уравнений (1). Используем для их решения такой инструмент, как якобиан. Пусть J (z,x) = det (d " P } - якобиан системы уравнений (2) относительно переменных z1,... , zn. Для систем уравнений с вещественными либо комплексными переменными хорошо известна следующая Теорема 1. Пусть выполнено равенство J (z, x) = 0, тогда система уравнений (2) либо не имеет решения для каждого x в пространстве Czn, либо все её решения в этом пространстве неизолированные. Таким образом, суть теоремы состоит в том, что такие системы не могут иметь изолированных решений. Для систем с некоммутативными переменными ситуация с описанием множества решений сложнее, а именно получена следующая Теорема 2. Пусть для якобиана коммутативной системы (2) выполнено равенство J (z, x) = 0, тогда некоммутативная система уравнений (1) либо не имеет решений (в виде ФСР z = z(x)), либо имеет любое конечное число решений, либо бесконечно много решений. Суть теоремы 2 состоит в том, что равенство нулю якобиана не ограничивает свойств некоммутативной системы уравнений. Учитывая, что система f = 0, . . . , f = 0, из п одинаковых уравнений с п некоммутативными неизвестными z1 , . . . , zn, имеющая тождественно равный нулю якобиан, эквивалентна одному уравнению f = 0, сформулируем следствие: одно уравнение с некоммутативными неизвестными P1(z, x) = 0 может не иметь решений, а также иметь конечное и бесконечное число решений. В этом состоит фундаментальное отличие от одного уравнения над полем комплексных чисел, которое всегда имеет решения в виде аналитических функций.

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