Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Jc2 - 2 = Jc2 - 02 = (* + 0) (* - 0).
Таким образом, можно найти и второй корень: он равен —0.
Если К — числовое поле, допускающее погружение в R (поле действительных чисел) или в С (поле комплексных чисел), то 0 можно отождествить с некоторым действительным или комплексным числом.
Пример. В предыдущем примере 0= Y2= 1,41421... .
Числа, являющиеся корнями алгебраических уравнений (т. е. уравнений вида f{x) = 0, где /—многочлен) с рациональными коэффициентами, называются алгебраическими.
Можно доказать, например, что число я не является алгебраическим. 258
Часть III. Алгебраический подход
В том же самом смысле термин алгебраический используется и применительно к полю функций.
Пример. Пусть Q(x) —поле рациональных дробей с рациональными коэффициентами. Расширим это поле с помощью функции у, такой, что
У = X у2 + 1;
эта функция является алгебраической.
Формальный ряд не следует смешивать с функцией, которую можно связать с этим рядом (ср. начало § 16.1). Рядом можно воспользоваться для представления той или иной функции, если только мы умеем сопоставить данному ряду его сумму. В классическом анализе пользуются «обычной» суммой, определенной в случае, когда ряд сходится; тогда можно найти радиус сходимости и т. д.
Мы, однако, останемся на чисто формальной точке зрения. При таком подходе естественно говорить, что формальный ряд, удовлетворяющий (конечному) алгебраическому уравнению, является алгебраическим.
Наконец, мы будем употреблять слово алгебраический в том же самом смысле и для некоммутативных рядов.
16.2.1. Системы уравнений специального вида
Пусть X = {xi \ 1 ^ і ^ m} — базовый алфавит, а 51 = = {Л/11 ^ } ^ п) — алфавит, символами которого обозначаются многочлены или формальные ряды из Q [[X*]]. Пусть, далее, Oj- — многочлены над Q [(? U X}*].
Будем рассматривать системы уравнений вида Aj = Oj, / = = 1, ..., и; решения их мы будем искать в Qn[[X*]].
Системы уравнений, рассматривавшиеся в гл. XI, являются по существу частным случаем таких систем (обоснование этого утверждения будет дано ниже).
Будем считать, что многочлены Oj удовлетворяют «условию повышения степени» (см. выше, п. 16.1.10).
Указанные системы можно решать методом последовательных приближений. Этот метод основан на следующей теореме:
Теорема. Пусть E — полное метрическое пространство и / — стягивающее отображение E в себя. Тогда уравнение х = f(x) имеет точно одно решение а и для произвольной точки ха е= E последовательность X0, f(xо), f(f(x0)), ... сходится к а.
Доказательство этой теоремы для общего случая предоставляется читателю в качестве упражнения. В том частном случае, который нас здесь интересует, а именно в случае ограниченного пространства, достаточно заметить, что последовательность fn(E) является убывающей и диаметр множества /"(?) не превосходит %п, где К имеет тот же смысл, что и в п. 16.1.10. Гл. XVI. Алгебраические языки
259
Замечание. В примерах гл. XI мы брали в качестве Xo ан-нулятор, которому в обозначениях данной главы соответствует Oe. Мы поступали так из соображений удобства. В действительности значение Xo можно выбрать произвольно, однако в этом случае нам, возможно, придется иметь дело с «лишними» выражениями.
Пример. Вернемся к «бесскобочной» і рамматике S = aSS + Ь, рассмотренной в гл. XI, однако возьмем другое начальное значение, например:
50 = а
51 = а3 + Ь
52 = а (а3 + Ь) (а3 + Ь) f 6 =
= a1 + a4b + aba3 + ab2 + b.
Как видим, появляется «утяжеленная» последовательность Sr, где Sr r-эквивалентно «хорошему» значению (получаемому при S0 = 0).
Теорема. Для алгебраической системы уравнений A1 = O1, /= 1, ..., п,
где во всех многочленах а, коэффициенты при е, Ai, ..., An равны нулю, существует ровно одна п-ка рядов из q [[x*]], которая удовлетворяет этой системе (и которую можно получить путем последовательных приближений).
§ >6.3. приложения к языкам
Возьмем в качестве Q кольцо целых чисел Z. Некоторые примеры приложений систем уравнений к языкам были приведены в гл. XI. Сейчас мы укажем интерпретацию в терминах языков некоторых результатов этой главы.
16.3.1. Вычитание языков
Рассмотрим некоммутативное уравнение
(F) S = а — SbS
и следующие приближения:
S'01 = а,
S1" = а — S{0)bSi0) = а — aba, S'21 = а - S0)bS{1) = а - {а - aba) b(a- aba) =¦ = а — aba + 2 ababa — abababa, 260
Часть III. Алгебраический подход
Формальный ряд, являющийся решением уравнения (F)1 имеет как положительные, так и отрицательные коэффициенты.
Положим 5 = S+ — 5" и подставим это выражение в (F). Имеем
S+ -S~ = a-{S+- S~) b (S+ - S~),
откуда
S+ -S~ ={a + S+bS~ + S~bS+) - (S+bS+ + S~bS~).
Рассмотрим теперь систему
S+ = a + S+bS~ + S~bS+,
(FO
S- = S+bS+ + S~bS~.
Уравнения системы (F') имеют положительные коэффициенты, и (F') допускает в качестве решения пару рядов с положительными коэффициентами; обозначим эту пару через (ст+, ст~). Тогда, если ст— формальный ряд, являющийся решением уравнения (F), то
