GREIBACH NORMAL FORM OF CONTEXT-FREE LANGUAGES: TNE ANALITIC APPROACH

Abstract

Context-free languages are consider as formal power series, which are solutions of the polynomial equations sys- tems with noncommutative variables respectively multiplication. It is suggested to investigate these systems in Greibach normal form, that allows to research it more effectively. Commutative images of languages and defining systems are described in complex domain.

Full Text

Формальным языком 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).