КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ В НОРМАЛЬНОЙ ФОРМЕ ГРЕЙБАХ: АНАЛИТИЧЕСКИЙ ПОДХОД

Аннотация

Контекстно-свободные языки рассмотрены как формальные степенные ряды, являющиеся решением сис- темы полиномиальных уравнений с некоммутативными относительно умножения переменными. Предложено изучать эти системы в нормальной форме Грейбах, что позволит более эффективно использовать аналити- ческие методы. Описаны коммутативные образы контекстно-свободных языков и определяющих их систем уравнений в комплексной области.

Полный текст

Формальным языком L называют множество цепо- чек в алфавите {x1, …, xn}, выделенных с помощью конечного набора правил. Такие цепочки, принадле- жащие свободной полугруппе {x1, …, xn}*, называются грамматически правильными предложениями (над словарем), а конечное множество правил, с помощью которых выделяются эти цепочки, называют грамма- тикой. Таким образом, формальный язык определяет- ся совокупностью соответствующих правил и спосо- бом выделения цепочек с помощью этих правил. вой части подстановки, сопоставляется уравнение zj = pj (x, z), где pj(x, z) = fj1(x, z) + … + fj q j (x, z). Та- ким образом, кс-грамматике соответствует система полиномиальных уравнений zj = pj (x, z), j =1, …, m, (1) называемая системой уравнений Хомского- Щютценберже, а кс-языком называется первая компо- нента zj ее решения (z1(x), …, zm(x)) [3; 4], получаемого методом последовательных приближений: Практически важный класс формальных языков z (k+1) j = pj(x, z(k) j ), z (0) = 0, j = 1, …, m, образуют контекстно-свободные языки (кс-языки), ( k ) ( k ) (k ) являющиеся мощным средством моделирования естегде z = (z i ,..., zm ); 0 - нулевой моном, такой, что ственных языков и языков программирования [1-3]. Обозначим W = {x1, …, xn} È {z1, …, zn} свободную полугруппу с операцией умножения над «расширен- ным» алфавитом {x1, …, xn, z1, …, zn}. Словарем языка является конечное множество 0 · u = u · 0 = 0 для любого монома u. В результате итераций компоненты zj выражаются формальными степенными рядами, причем кс-язык есть тот из них, который представляет выделенный символ z1: X = {x1, …, xn} слов языка, называемое терминальным множеством, а Z = {z1, …, zm} - множество вспомогаz1 = å< z1 , wi > wi , i (2) тельных символов zj, необходимых для задания грам- матических правил, называемое нетерминальным множеством; W* = (X È Z)* - соответствующая свобод- ная полугруппа относительно операции конкатенации. Дополним ее операцией формального сложения «+» мономов из множества W* (вместо суммы можно взять где < z1, wj > - числовой коэффициент при мономе wj от некоммутативных переменных x1, …, xn (формаль- ная сумма всех мономов и образует кс-язык). Условие, что язык является контекстно- свободным, состоит также и в том, что многочлены p (x, z) не содержат мономов z и e, где e - пустая цеj j объединение « È », следуя [1]), а также коммутативной операцией умножения мономов на (целые) числа. Таким образом, можно рассматривать не только мно- гочлены, но и формальные степенные ряды с число- выми (как правило, целыми) коэффициентами от не- коммутативных переменных. Кс-грамматика есть совокупность правил подста- новки, которые каждому нетерминальному символу zj ставят в соответствие некоторый моном от терми- нальных и нетерминальных символов: z j ® f j1(x, z),...,z j ® f jq j (x, z) , причем z1 - особый символ, играющий роль начала предложения в языке. Применение к нему произволь- ного числа подстановок порождает всевозможные правильные предложения языка. Важной задачей теоретической информатики и ее приложений в теоретическом программировании яв- ляется изучение структуры кс-языков и ее связи со структурой порождающих грамматик. Правилам подстановки ставится в соответствие система полиномиальных уравнений [3]: каждому вспомогательному символу zj, содержащемуся в лепочка. Таким образом, существование и единственность решения системы (1) обеспечивается ее специ- фической структурой и методом последовательных приближений. Система уравнений Хомского-Щютценберже впервые изучалась аналитическими методами в рабо- тах К. В. Сафонова (например, [3]). Предложенный им подход состоял в изучении систем полиномиальных уравнений произвольной степени от многих перемен- ных в комплексной области, что, естественно, сопря- жено со значительными трудностями. Авторы предлагают изучать вместо системы урав- нений Хомского-Щютценберже эквивалентную ей сис- тему в нормальной форме Грейбах [5. С. 127], в кото- рой все многочлены имеют вторую степень по пере- менной z; переход к нормальной форме Грейбах всегда возможен за счет увеличения, быть может, числа пере- менных. Для уравнений второй степени аналитические методы исследования представляются более перспек- тивными: их эффективность в большей мере зависит от степени уравнений, чем от числа переменных. Более точно, нормальная форма Грейбах систе- мы (1) подразумевает, что все входящие в нее многочлены имеют вид pj (x, z) = fj (z) + gj (x, z) + hj(x), где fj (z) - квадратичная форма от переменных z1, …, zn, многочлен gj (x, z) линеен по z1, …, zn , а многочлен hj(x) от них не зависит [5. С. 127]. А значит, можно считать, что система (1) имеет следующий вид: zj = fj(z) + gj (x, z) + hj(x) = 0, j = 1, …, m. (3) Нам понадобится понятие коммутативного образа формального ряда (многочлена) [2; 3]. А именно, по- ставим в соответствие формальному степенному ряду (многочлену) ряд (многочлен) с комплексными пере- менными, задав отображение терминальных xi и нетерминальных zi символов из множества X È Z в множество комплексных переменных, причем за нетерминальными переменными zi оставляем прежние обозна- чения, а терминальные символы xi отображаем в ком- плексные переменные zi соответственно, тогда Учитывая относительную простоту структуры ли- нейных языков и конструкции диагонали, можно сде- лать вывод о том, что структура широкого класса кс- языков, описанных в теореме 1, является достаточно простой. Доказательство. Рассмотрим корни системы (3) следующим образом: будем считать переменные x и z1 комплексными параметрами, а остальные корни z[1] = (z2, …, zn) = z[1](x, z1) - зависящими от этих па- раметров. Условие теоремы 1 означает, что ни при каких значениях параметров корни системы (3) не стремятся к бесконечности (как это бывает, например, когда старший коэффициент многочлена при некото- ром значении параметра обращается в нуль). Следова- тельно, при всех значениях параметров x и z1 число корней z(k) [1] (x, z1) подсистемы pj (x, z) = 0, j = 2, …, n m+ n (x, z) Î Cx, z . Таким образом, получаем фиксированс учетом кратностей mk одно и то же, а потому возный гомоморфизм, который ставит в соответствие формальному ряду (2) его коммутативный образ - можно корректно определить результант этой подсистемы относительно уравнения p1 (x, z) = 0: сходящийся в окрестности нуля степенной ряд от комплексных переменных: 1 Õ 1 P(x, z ) = pmk (x, z1 , z 1 ( k ) [1](x, z )), где ci(r) = åak z k , k k где в произведение входят все корни уравнения. В силу симметричной зависимости этой функции от корней и алгебраичности самих корней, результант k k1 kn ak z 1 n = ak ,...,k z1 ...z1 , также является симметричной алгебраической функ- цией, т. е. многочленом. ak = å # x1 ( wi ) = k1 ,...,# xn ( wi ) =kn < r, wi > , Согласно теореме о результанте системы символ #c(d) означает число вхождений символа c в моном d. [6. С. 238], кратность корня (0,0) системы (3), равная 1, совпадает с кратностью корня z1 = 0 многочлена Итак, рассмотрим систему уравнений (3). Если в P(x, z1 ) при x = 0. А значит, для многочлена P(x, z1 ) ней fj (z) º 0 при всех j, то эта система - линейная, и порождаемый ей язык принадлежит к простейшему классу линейных языков [1; 2]. Однако важно, что существует связь с кс- и линейными языками, точнее, выполняется условие P(0, 0) = 0, ¶P(0, 0) image ¶z1 ¹ 0. между их коммутативными образами. А именно, рассмотрим коммутативный образ кс- языка z1: Отсюда следует, что алгебраическая функция z1, определяемая многочленом P, является диагональю некоторой рациональной функции от переменных x0, ci(z1) = a xk = a xk1 ...xkn , (4) x1, …, xn [7]. Поскольку каждая голоморфная в нуле k k1 ,..., kn 1 n который является алгебраической функцией, а также коммутативный образ рациональная функция является коммутативным об- разом соответствующего линейного языка, теорема 1 доказана. ci(L) = å k0 ³0,k ³0 0 Lk ,k x0k0 xk (5) Порождающая кс-язык система уравнений (3) в нормальной форме Грейбах позволяет установить и некоторого линейного языка над терминальными символами x0, x1,…,xn, являющийся рациональной функ- цией. Будем называть ряд (4) диагональю ряда (5), если при всех k1,…, kn, выполнено условие другие свойства кс-языков, например, является дан- ный формальный степенной ряд контекстно- свободный языком или нет. Сгруппируем коммута- тивный образ формального языка в ряд по однород- ным многочленам: 1 n 1 1 2 n ak ,..., k = Lk , k , k ,..., k , ci(z ) = (a) (x), (7) и в следующей теореме установим, для каких именно кс-языков коммутативные образы являются диагона- лями линейных языков. Теорема 1. Если однородные многочлены второй степени f2(z), …, fn(z), входящие в систему (3), не зави- 1 å j j где (a)j(x) - однородный многочлен степени j. Достаточно установить, что ряд (7) удовлетворяет уравнению степени 2, поскольку такую степень имеет система (3). Возводя ряд (7) в квадрат, получим ряд (2) сят от переменной z1, и система уравнений (ci(z1))2 = Sj (a)j (x). Тот факт, что оба ряда, будучи fj(z) = 0, j = 2, …, n (6) имеет единственный нуль z = 0, то коммутативный образ кс-языка, порожденного системой (3), является диагональю некоторого линейного языка. умноженными на многочлены, дают в сумме тождественный нуль, означает, что достаточно длинные от- резки этих рядов линейно зависимы. Таким образом, получается следующая теорема. Теорема 2. Для того чтобы ряд по однородным многочленам (7) удовлетворял полиномиальному уравнению степени 2, необходимо и достаточно, что- бы при всех j ³ j0, l ³ l0 выполнялось равенство Семенов, А. Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик / А. Л. Семенов // Доклады АН СССР. Т. 212. 1973. С. 50-52. Сафонов, К. В. О возможности вычислительного image (a) j (x) ... (a) j +l (x) (a) j (2) (x) ... (a) image l j + ( 2) (x) распознавания контекстно-свободных языков / К. В. Са- (a) (x) ... (a) (x) (a) (2) (x) ... (a) (x) j +1 j +l +1 j +1 j +l +1 º 0, фонов // Вычислительные технологии. 2005. Т. 10. ... ... ... ... ... ... № 4. С. 91-98. Сафонов, К. В. О синтаксическом анализе и про- j q (x)...(a) j q l (x) (a) (2) (x)...(a) j q l (2) (x) + + + где число q = 2l + 1. j + q + + блеме В. М. Глушкова распознавания контекстно- свободных языков Хомского / К. В. Сафонов, О. И. Его- Таким образом, нормальная форма Грейбах систем уравнений, порождающих кс-языки, имеет ряд пре- имуществ, связанных с тем, что эти уравнения имеют степень не выше второй. Так, нормальная форма Грейбах позволяет установить важную связь кс- языков с линейными языками (теорема 1), а также по- лучить фундаментальное условие, характеризующее кс-языки (теорема 2).