Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
определили сложение и умножение многочленов, можно теперь естественным образом определить композицию многочленов:
f(gl. • • gn)1)-
Пример. Пусть f(XltX2) = X1X2-, тогда f(gi,g2) = gig2¦ Отсюда видно, что умножение может рассматриваться как частный случай композиции.
') Т. е. результат подстановки в / многочленов gь ..., gn вместо хи ..., хп соответственно. — Прим. ред. Гл. XVI. Алгебраические языки
249
Пусть буквы Ai, ..., An, образующие алфавит її, обозначают переменные, принимающие значения в Я[7"*], где T = {tu ..., tm).
Пусть, кроме того, имеется еще отображение о алгебры й[її*] в й[(її U 7")*], определяемое условиями
о: Aj-^gjitl.....tm, A1, ..., Atl), j = 1, ..., п.
Это отображение индуцирует некоторое отображение Qn [Г*] в себя следующим образом: я-ке многочленов [si, ..., s„] ставится
В соответствие я-ка многочленов .....tm, Si, ..., Sn), ...
•••>Sn (tu ..., tm, Si, ..., s„)].
Пример.
її = {Л, В}, T = {а, Ь},
A-^a + AbB + BbA,
В -»¦ AbA + BbB.
Паре многочленов (0,0) соответствует здесь пара (а, 0), паре (Ь, а) — пара (a + b2a + ab2, b3 + aba) и т. д.
16.1.3. Формальные ряды
Построим теперь расширенную алгебру Й[[А'*]], содержащую Q [Ar*] в качестве подалгебры. Элементами этой алгебры будут формальные ряды
a Ji+ ... +anfn+ ...,
которые могут содержать неограниченное число неподобных членов с ненулевыми коэффициентами. Сложение рядов определяется так же, как и сложение многочленов.
Чтобы определить умножение рядов, будем упорядочивать их по возрастанию степеней (длин) цепочек и представлять каждую цепочку всеми способами в виде произведения (конкатенации)
двух сомножителей. Цепочкаh = х х, ... х. представляется либо
11 2 'k
В виде eh, либо В виде (х{ ^xi . . . Xi^j и т. д.
Цепочка h в произведении двух рядов будет иметь коэффициент 2O1P/, гДе сумма берется по всем возможным разбиениям цепочки h на два сомножителя, первый из которых — член первого ряда, а второй — член второго ряда. Таким образом, для того чтобы определить коэффициент цепочки h в произведении двух рядов, требуется перебрать конечное (и заранее известное) число их членов. Следовательно, произведение рядов определяется эффективно.
Легко видеть, что Q [[Ar*]] — кольцо. Эта расширенная алгебра содержит подмножество, изоморфное кольцу QfAr*]1), и мы будем
') Это подмножество состоит из тех рядов, у которых лишь конечное число коэффициентов отлично от нуля. — Прим. ред. 250
Часть III. Алгебраический подход
отождествлять это подмножество с самим Q [Л*], что равносильно трактовке многочлена как «вырожденного ряда».
16.1.4. Норма пространства формальных рядов
Назовем порядком формального ряда наименьшую из длин членов ряда — непустых цепочек с ненулевыми коэффициентами, остающихся после приведения подобных членов. Порядок нулевого ряда (т. е. такого, у которого все коэффициенты равны нулю) будем считать по определению равным +оо.
Пример. Пусть Х = {х,у}\ ряды выписываются по возрастающим степеням.
Ряд
е + ху + х2у2 + ... +хпуп+ ...
содержит пустую цепочку е, и его порядок равен нулю.
Ряд
XX+ уу + хух + уху + . . . + XykX + ухьу + . . . имеет порядок 2 (длина, или степень цепочек хх и уу).
Сложение. При сложении двух рядов возможны следующие случаи:
— порядок одного ряда строго меньше порядка другого; тогда порядок суммы равен меньшему из этих двух порядков;
— оба ряда имеют одинаковый порядок; тогда, если члены низших степеней не уничтожаются, порядок суммы остается таким же, а если члены низших степеней взаимно уничтожаются, порядок суммы увеличивается.
Случай, когда хотя бы один из рядов оказывается нулевым, не ведет к дополнительному усложнению.
В результате мы получаем следующую лемму:
Лемма 1. Порядок суммы рядов (s) и (s') удовлетворяет неравенству
ord [(s) + (s')] > min [ord [(s)], ord [(s')]] ')•
Умножение. При перемножении двух рядов их члены, имеющие минимальные степени, дают член произведения, имеющий минимальную степень, если только Q не содержит делителей нуля. В противном случае суммарная степень произведения можег оказаться больше суммы степеней сомножителей. Это дает такую лемму:
Лемма 2. Порядок произведения рядов (s) и (s') удовлетворяет неравенству
ord [(s) (s')] > ord [(S)] + ord [(s')];
') ord означает порядок. — Прим. ред. Гл. XVI. Алгебраические языки
251
в случае, когда кольцо Q является областью целостности, неравенство можно заменить равенством.
Норма в кольце Q [[^*]]- Возьмем любое действительное число, строго большее единицы, например 2. Определим норму ряда (S)—обозначение val[(s)] — следующим образом:
val[(S)] = 2-°rd[<s)1.
Примеры. Для рядов, фигурировавших в предыдущих примерах, получим соответственно
2° = 1 и 2-2 = |.
В силу нашего определения для нулевого ряда («о) имеем
val [(S0)] = 2- = 0. Сложим ряды (s) и (s'); тогда
val [(s) + (s')] = 2_ord [<s)+<s,)';
но поскольку
ord [(s) + И] > min [ord [(s)], ord [fs')] ],
мы получаем следующую лемму: Jl е м м а 3.
