Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Из определения ясно, что опорное множество адамаровского произведения двух рядов совпадает с пересечением опорных множеств этих рядов:
supp (Ct1 О о2) = supp (CT1) ft supp (ст2).
Теорема Юнгена, обфбщенная на некоммутативные функции (ряды), приобретает следующий вид.
Теорема (Юнген — Шютценберже). а) Если Supp(CT1)—рациональный язык и Supp(CT2) — рациональный язык, то supp (стіО^г) — тоже рациональный язык.
б) Если supp(CTi)—рациональный язык и supp (стг) — алгебраический язык, то supp (стіО^г)—алгебраический язык. 264
Часть III. Алгебраический подход
в) Если supp (сті) —алгебраический язык и supp (02) —алгебраический язык, то supp (стіО^г) может не быть алгебраическим языком.
Эта теорема обобщает также результаты, относящиеся к пересечениям КС-языков и А-языков.
Имеет место следующее важное свойство.
Рассмотрим гомоморфное отображение цепочек некоторого языка на язык, задаваемый рядом с коммутативными переменными ')• При таком отображении указанные выше свойства рядов сохраняются.
Ясно, что это отображение преобразует систему некоммутативных уравнений в классическую систему.
Можно доказать, что верно и обратное.
§ 16.4. упражнения
1. Функция ф, определенная на кольце U = {a,b,c, ...} и принимающая действительные значения, называется нормой, если она удовлетворяет следующим условиям:
1) (Vaf=?/)[q>(a)>0],
2) ф(а) = 04фа = 0,
3) ф(а + &)<ф(а) + ф(&),
4) ?(1)=1,
5) ф(а&)<ф(а)ф(&).
Доказать, что val [(s)] — норма для Q [[Z*]].
2. Показать, что выбор числа, превосходящего 1, которое служит для построения функции val [ (s) ] (у нас в качестве такого числа была выбрана двойка), не имеет принципиального значения.
3. Доказать утверждение п. 16.1.9, а именно: подстановка рядов (Sj) в произвольный ряд возможна, если ряды (Sj) квазирегу-лярны.
4. Описать порождение языка
{арЬ9 I р, q > 0, р Ф q)
— посредством системы уравнений,
— посредством КС-грамматики.
§ 16.5. ПРИМЕНЕНИЕ «ЯЗЫКОВЫХ» УРАВНЕНИИ В КОМБИНАТОРНОЙ ГЕОМЕТРИИ
Теория формальных грамматик имеет интересные приложения в некоторых вопросах комбинаторной геометрии и комбинаторного анализа. Мы ограничимся в этой связи разбором примера, пока-
') Точнее, свободной полугруппы на свободную полугруппу с одной образующей. — Прим. ред. Гл. XVI. Алгебраические языки
265
зывающего, как с помощью формальных грамматик можно по-новому подойти к решению одной классической задачи.
16.5.1. Задача о разбиении многоугольника
Пусть имеется жорданов многоугольник (т. е. топологический многоугольник, разбивающий плоскость на внешнюю и внутреннюю области) с помеченными вершинами; спрашивается, сколькими разными способами можно разбить его на треугольники посредством диагоналей, не имеющих общих точек, кроме вершин?
Пример. В случае пятиугольника решение очевидно: пятиугольник допускает пять различных разбиений. Вот они:
Наметим сначала путь «классического» решения сформулированной задачи. 266
Часть III. Алгебраический подход
Пусть имеется жорданов m-угольник, и пусть /(т)— число его возможных разбиений. Рассмотрим и-угольник P и определим с помощью функции / число разбиений, имеющих один фиксированный общий треугольник. Если выбросить из P этот общий треугольник, останутся два многоугольника, имеющие р и q сторон соответственно, причем
p + q = n+ 1.
Следовательно, искомое число есть f(p)f(q).
Если один из двух «малых» многоугольников пуст, данное число равно / (п — 1).
Полагая /(2)= 1, получаем для всех п = 2, 3, ... единое выражение
f(p)f(q); p + q = n+ 1.
Фиксируем одну из сторон п-угольника A\Az.. .An, например AiA2; произвольную вершину, отличную от Ai и A2, будем обозначать через Ai.
Все треугольники AiA2Ai различны, и всякая триангуляция, содержащая AiA2Ai, отличается от триангуляции, содержащей AiA2Aj, і ф /. Суммируя по і, мы получим следующую рекуррентную формулу:
f(n) = f(2)f(n-l)+ ... +f(i)f(n-i+ 1)+ ... +f(n- 1)/(2).
В случае треугольника имеем /(3)= 1, что позволяет последовательно вычислять f(n) для любых п.
Пример.
/(4) = /(2)/(3) + /(3)/(2) = 2,
/(5) = /(2)/(4) + /(3)/(3) + /(4)/(2) = 5.
Теперь попытаемся определить производящую функцию */ = / (2) X2 + / (3) Xz + ... + / (п) хп + ...,
такую, чтобы коэффициент при Xn давал f(n). Предыдущие рассуждения не подсказывают пути к этому, и создается впечатление, что необходимо прибегнуть к какому-то «трюку». Между тем использование формальных грамматик приводит к весьма естественному решению. Гл. XVI. Алгебраические языки
267
16.5.2. Решение задачи о разбиении многоугольника с помощью грамматики
Основная идея состоит в том, чтобы построить грамматику, порождающую многоугольники, разбитые на треугольники, так, как порождаются цепочки формального языка. Если эта грамматика будет однозначной, то она выдаст — в качестве «побочного продукта» — пересчет треугольников, т. е. число /(«).
Рассмотрим «бесскобочную» грамматику
S -*• aSS, S-*b.
Эта грамматика однозначна. Дадим ее символам и правилам следующую интерпретацию.
