Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
i = 0, ..., to и всех / = 1, ..., п. Но Lj‘0+I) =
— это множество рсех тех цепочек, которые получаются из членов fj, если подставлять в них вместо h цепочки из b\l°\ вместо — цепочки из Lи т. д. (причем разные вхождения одного и того же h' — даже в один член — могут замещаться разными цепочками). Будем теперь в произвольные деревья высоты 1, имеющие вид
•?/
/\
ос1 • • • • • oct
где О] ... щ — член fj, подставлять вместо каждого
вхождения каждого ?/', /'= 1........п, какое-либо (1Г, 20-
дерево грамматики Г, имеющее высоту, меньшую или равную t0, и такое, что геУ. Полученное множество деревьев обозначим А4<0/. По предыдущему множество
{Прк^(Г) \Т е Mioj} есть как раз Lj*0+1). Однако Mloj— это множество (?/, л:)-деревьев в Г высоты, не превосходящей /0 + 1. таких, что х е V\ Итак, наше утверждение доказано.
Из установленного в предыдущем абзаце факта немедленно вытекает, что L] (Г) = Ls для любого /=1, ..., п.
Упомянем еще об одном способе представления наименьшего решения нормальной системы уравнений — с помощью так называемых формальных степенных рядов.
Фиксируем некоторый пересчет цепочек в алфавите V: х0, хи ..., хп......в котором более короткие це-
почки предшествуют более длинным, так что, в частности, х0 — А. Фиксируем также некоторую функцию f(n), определенную на натуральном ряду и принимающую в качестве значений натуральные числа. Выраже-
оо
ние 2if(n)x„, или, иначе,
/1=0
ДО)х0 + /(1)х1 + ... +/(я)х„ +
СИСТЕМЫ УРАВНЕНИЙ В ЯЗЫКАХ
211
будем называть некоммутативным формальным степенным рядом (или для краткости просто формальным рядом) в алфавите V. Множество {Xi | f (i) > 0} назовем опорным множеством данного формального ряда.
Многочлен без переменных, коэффициентами которого служат цепочки в V, можно рассматривать как частный случай формального ряда, если заменить в нем знак U знаком +, расположить члены соответствующим образом и «привести подобные».
Для заданной конечной последовательности натуральных чисел р = (п0, пи ..., nN) будем обозначать через Rp множество всех формальных рядов в алфавите V, у которых коэффициенты при Хо, хи ..., xN равны п0, пп ..., nN соответственно. (В частности, последовательность р может быть пустой — тогда Rp есть множество всех формальных рядов в У.) Если считать окрестностями ряда г множества RPo, Rp , ..., RPn, ..., где pN — последовательность первых jV -f- 1 коэффициентов г, то множество всех формальных рядов в словаре V становится топологическим пространством. Сходимость в этом пространстве означает, очевидно, следующее: последовательность рядов г\, ..., г$, ... сходится к ряду г, если для каждого N = 0, 1, ... найдется такое S = 1, 2, ..., что для любого s = S, 5+1, ... имеют место равенства: fs(0) = f(0), fs(l) = f(\), ..., fs(N) = ~f(N), где fs(n) и f(n) означают коэффициенты при хп в рядах rs и г соответственно.
Легко убедиться, что если последовательность рядов г 1, ..., rs, ... сходится к ряду г, то опорное множество г является пределом последовательности опорных множеств г и ..., rs,
Вернемся теперь к системе уравнений (*), наложив на нее некоторые ограничения, а именно: (1) левые части уравнений не должны содержать членов вида
(2) ни один из многочленов /,? не должен содержать
*) Множество М называется верхним (нижним) пределом последовательности множеств, если М есть множество всех элементов, принадлежащих бесконечному числу членов последовательности (соответственно всем членам последовательности, кроме, быть может, конечного их числа). Если верхний предел совпадает с нижним, он называется пределом последовательности.
212 ДОПОЛНИТЕЛЬНЫЕ С&ЕДЕНИЯ О 6-ГРАММАТИКАХ [ГЛ. 6
переменной gr, (3) при / ф 1 в fj не должно быть пустого члена. Если перейти к грамматике, отвечающей системе (*), то порождаемый такой грамматикой язык и при сформулированных сейчас ограничениях может быть произвольным ОБ-языком (следствие из теоремы 4.3, лемма 4.1).
Определим для каждого /= 1, ..., п последовательность формальных рядов (являющихся многочленами)
gf\ gip......gip, ... следующим образом: (I) g<°> есть
сумма свободных членов многочлена fj-, (II) g(/+I) полуг
чается из ff подстановкой g\l)....gM вместо 1,, ...,
соответственно с последующим формальным раскрытием скобок и приведением подобных.
Непосредственно ясно, что для любых I, j (/==0, 1,.. 1=1, п) опорное множество ряда gp есть Lp. В то же время из наложенных на систему (*) ограничений (1) — (3) следует, что каковы бы ни были г* = 0, 1,... и /=1, ..., п, коэффициенты при цепочках длины, не большей i, во всех рядах gp, g(/i+I), g^’+2), ... совпадают. Действительно, цепочки длины, не большей единицы, в любом многочлене gp — это в точности свободные члены fj длины 1; если утверждение справедливо для некоторого /0, то для i0 -f 1 оно вытекает из того очевидного факта, что каждая цепочка Длины i0 +1 в многочлене g(yi+I) при любых i и / либо является свободным членом ft, либо получается из некоторого члена fj при подстановке вмЗЬто переменных каких-либо членов g(/>, gW, являющихся цепочками длины, не большей i0, а такие члены у всех многочленов gp\ glp+l\ gp+2), ... по индуктивному предположению оди« наковы. Таким образом, если обозначить через г/ (/ = 1, ..., ft) формальный ряд, в котором коэффициенты при каждой цепочке длины i (г = 0, 1, ...) такие же, как в gp, то к этому ряду будет сходиться последовательность gp, gp,... Однако опорное множество ряда?</>
