Analitic approach to context-free languages in the greibach normal form.pdf Словарем языка является конечное множество X = {ж1,. .. , жп} слов языка, называемоетерминальным множеством, а Z = {z 1, ... , zm} - множество вспомогательныхсимволов Zj, необходимых для задания грамматических правил, называемое нетерминальныммножеством; W* = (X U Z )* - соответствующая свободная полугруппаотносительно операции конкатенации.Кс-грамматике соответствует система полиномиальных уравненийZj = Pj (x ,z ),z = 1 , . . . ,m , (1)называемая системой уравнений Хомского - Щютценберже, а кс-языком называетсяпервая компонента z1 ее решения (z1(x ),... , zm(x)), получаемого методом последовательныхприближений. В результате итераций компоненты Zj выражаются формальнымистепенными рядами.В настоящей работе предлагается изучать вместо системы уравнений Хомского -Щютценберже эквивалентную ей систему в нормальной форме Грейбах, в которой всемногочлены имеют вторую степень по переменной z; переход к нормальной формеГрейбах всегда возможен за счет увеличения, быть может, числа переменных. Дляуравнений второй степени аналитические методы исследования представляются болееперспективными: их эффективность в большей мере зависит от степени уравнений,чем от числа переменных.Более точно, нормальная форма Грейбах системы (1) подразумевает, что все входящиев нее многочлены имеют вид p j(ж, z) = fj(z) + g j(ж, z) + hj(ж), где fj( z ) - квадратичнаяформа от переменных z1, ... , zm, многочлен gj (ж, z) линеен по z1, ... , zm, амногочлен hj(ж) от них не зависит. А значит, можно считать, что система (1) имеетвидzj = f j ( z )+ gj (x,z) + hj (x ),j = 1,. . . ,m. (1*)Поставим в соответствие формальному степенному ряду (многочлену) ряд (многочлен)с комплексными переменными, задав отображение терминальных ж^ и нетерминальныхzi символов из множества X U Z в множество комплексных переменных.Получаем фиксированный гомоморфизм, который ставит в соответствие формальномуряду его коммутативный образ (2) - сходящийся в окрестности нуля степеннойряд от комплексных переменныхci(r) = X akzk,k (2)гдеBxi(Wi) = kl,...,BXn(Wi)=knсимвол ftc(d) означает число вхождений символа с в моном d.Рассмотрим коммутативный образ кс-языка z1ci(z1 ) = akxk = akl,...,knxkl XTn, (3)который является алгебраической функцией, а также коммутативный образci(L) = ^ Lko,k x0k0 xk (4)ko ^0,k^0некоторого линейного языка над терминальными символами Xo, X1 , , Xn, которыйявляется рациональной функцией.Будем называть ряд (3) диагональю ряда (4), если при всех k1, , kn выполненоусловиеТеорема 1. Если однородные многочлены второй степени / 2(z), , / n(z), входящиев систему (1*), не зависят от переменной z1 и система уравненийимеет единственный нуль z = 0, то коммутативный образ кс-языка, порожденногосистемой (1*), является диагональю некоторого линейного языка.Порождающая кс-язык система уравнений (1*) в нормальной форме Грейбах позволяетустановить, является данный формальный степенной ряд контекстно-свободнымязыком или нет. Сгруппируем коммутативный образ формального языка в ряд по однородныммногочленамгде (a)j(x) - однородный многочлен степени j . Достаточно установить, что ряд (5)удовлетворяет уравнению степени 2, поскольку такую степень имеет система (1*). Возводяряд (5) в квадрат, получим ряд (ci(z1))2 = (a)2(x). Тот факт, что оба ряда,будучи умноженными на многочлены, дают в сумме тождественный нуль, означает,что достаточно длинные отрезки этих рядов линейно зависимы.Теорема 2. Для того чтобы ряд по однородным многочленам (5) удовлетворялполиномиальному уравнению степени 2, необходимо и достаточно, чтобы при всехj ^ j 0, l ^ l0 выполнялось равенствоЛ'(z) = 0 j = 2>- ,n >(5)(a)j (x) (a)j+i(x) (a)2(x) (a)2+ (x)(a)j+1(x) (a)j+i+1(x) (a)2+1(x) (a)2+i+1(x) = 0(a)j+q(X) (a)j+1+q(X) (a)2+q(x) (a)2+1+q(x)где q = 2l + 1.

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