Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
val [(s) + (s')] < max [val [(s)], val [(s')] ].
Примеры. Пусть ряд (s) начинается с х и ряд (s') начинается с ху. Тогда ряд (s) + (s') начинается с х. Имеем
val [(s)] = 2-', val [(s')l = 2-2,
val f(s) + (s')l = 2_1.
Если ряд (s) начинается с х -f ху +..., а ряд (s') начинается с — X + ху + ..., то
val [(5)1 = 2"1, val [(/)] = 2"1, val Rs) + ^)] = 2-2. Из леммы 2 вытекает также 252
Часть III. Алгебраический подход
Л е м м а 4. В кольце fi [[Ar*]]
val [(s) (s')] < val [(s)] • val [(s')].
Читатель докажет сам (упр. 1 из § 16.4), что функция val[(s)] является нормой для кольца Q [[A"*]].
16.1.5. Расстояние между рядами
Пусть даны два ряда (s) и (s'). Расстоянием между этими рядами (обозначение: d[(s), (s')]) мы назовем число
val [(s) - (s%
Это расстояние обладает следующими свойствами:
I. d [(S), (s)] = 0.
В самом деле, d [(s), (s)] = val [(s) - (s)] = val [s0] = 0.
II. d[(s),(s')) = d[(s'),(s)).
III. d [(s), (s")] < max [d [(s), (s')], d [(s'), (*")] ]•
Действительно,
(s) - (s") = [(s) - (s')] + [(s') - (s")];
остается применить лемму 3.
Заметим, что свойство III сильнее, чем неравенство треуголь ника:
Ilia, d [(s), (s")] < d [(s), (s')] + d [(s), (s")].
Свойства I, II и IIIa — обычные аксиомы расстояния; это оправдывает название, данное нами функции d. Пространство, в котором определено расстояние, удовлетворяющее этим аксиомам, называют метрическим; если же кроме IIIa выполняется более сильное неравенство III, то пространство называют ультраметрическим.
Поскольку расстояние между двумя рядами не может быть больше 1, пространство рядов ограничено-, оно имеет диаметр 1.
Итак, имеет место
Предложение. Пространство формальных рядов, в котором указанным выше способом введено расстояние, является ультраметрическим.
16.1.6. Предел последовательности рядов
Введя понятие расстояния, мы можем определить предел последовательности рядов. Пусть имеется последовательность формальных рядов (Si).....(Sp), ...; пусть (s)—фиксированный ряд
Если rf[(sp) — (s)] стремится к нулю, говорят, что последова тельность (Si), ..., (Sp), ... стремится к (s) (при р, стремящемся к бесконечности) или, иначе, что (s) есть предел этой последовательности. Гл. XVI. Алгебраические языки
253
Обозначим через Po, Pu ..., Pr, ¦¦¦ последовательность однородных многочленов, такую, что степень многочлена Pr равна г. Последовательность
Po,
Po+ Pu
Po + Pl + ... +Pr,
есть последовательность многочленов и, следовательно, последовательность рядов, стремящаяся (в определенном выше смысле) К ряду
Po + Pl+ ••• +Pr+
Пусть (si), (s2), ... — произвольные ряды порядков 1, 2, соответственно. Последовательность
(to) = Po + (Si), (U) = P0 +Pi +(S2),
(tr) = P0 + Pi+ ... +Pr + (sr+1) стремится к тому же ряду.
Будем говорить, что два ряда r-эквивалентны, если порядок их разности больше или равен г + 1. Можно сформулировать следующее
Предложение. Если в сходящейся последовательности рядов (t0), ..., (tr), ... заменить каждый ряд (tr) произвогьным r-эквивалентным ему рядом, то предел последовательности не изменится.
16.1.7. Полнота пространства ?[[X*]]
Пусть (si), (s2), ..., (sn), ... — бесконечная последовательность элементов в метрическом пространстве. Критерием Kouiu называется следующее условие:
(Ve > 0) (ЗЛО [p>N&q>N^>d [(Sp)1 (Sq)] < г].
Всякая сходящаяся последовательность удовлетворяет критерию Коши. Пространство, в котором всякая последовательность, удовлетворяющая критерию Коши (последовательность Kouiu), сходится, называется полным.
Покажем, что пространство Q [[X*]] является полным.
Пусть (sn) — некоторая последовательность Коши. Тогда можно найти номер пи начиная с которого все члены последовательности 1-эквивалентны, затем номер п2, начиная с которого все члены 2-эквивалентны, и т. д. 254
Часть III. Алгебраический подход
Теперь легко получить последовательность многочленов, сходящуюся к некоторому ряду (s), и показать, что последовательность (Sn) сходится к (s) ').
16.1.8. Квазирегулярность. Итерация
Назовем ряд квазирегулярным, если в нем коэффициент при пустой цепочке равен нулю. В частности, нулевой ряд является квазирегулярным.
Пусть (s)—квазирегулярный ряд; наименьшая из возможных степеней его членов не меньше единицы. Образуем ряд (s)2; наименьшая степень его членов не меньше двух. Аналогично для (s)3 и т. д. При р -> оо порядок ряда (s)p стремится к бесконечности.
Пусть (S0) — нулевой ряд. Из только что сказанного следует, что d [(s)р, (so)] стремится к нулю; стало быть, (s)p стремится к нулевому ряду.
Рассмотрим последовательность
(M = (S),
UA = (S) + (S)2,
(Z3) = (S) + (s)2 + (s)3,
Эта последовательность удовлетворяет критерию Коши и, следовательно, сходится к пределу, который мы обозначим через (s)*,
Для ряда (s)* имеют место следующие очевидные соотношения:
(s) + (s)2+ ... +(S)"+ ... =(S)',
(S) + (S)* (S) = (S) + (S) (S)' = (S)'.
Положим
(s') = е — (s); (s") = e + (s)*.
