Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
x)z=Z.
С помощью этого отображения мы можем определить ряд
г = Il (г, х)х,
X
в котором коэффициент при каждом члене X равен тому числу, которое отображение (г) сопоставляет данному члену. 190
Часть II. Некоторые замечательные классы языков
Пример. Пусть Vt = {а,Ь}. Выписывая члены ряда в порядке возрастания длин, а при равной длине — в лексикографическом порядке, мы получим
Е, а, ft, аа, ab, Ъа, bb, ааа, aab, aba.....
Коэффициент каждого члена определяется так: к числу, равному длине данного члена, прибавим 1 и возьмем остаток от деления этой суммы на 3. Это и есть коэффициент.
В нашем случае получится следующий ряд:
т — 1? + 2а + 2b + Oaa + Oab + Oba + Obb + Iaaa+ laaft + Iafta+____
Члены с нулевыми коэффициентами можно не выписывать.
Если (г) отображает Vt на (0, 1), т. е. если функция (г) является характеристической, то ряд называется характеристическим. Всякому ряду можно сопоставить характеристический ряд, сохранив все нулевые коэффициенты, а ненулевые заменив единицами.
Пусть имеется степенной ряд г; тогда множество цепочек с ненулевыми коэффициентами образует язык L, называемый опорным множеством данного ряда и обозначаемый через
L = supp (г).
11.2.2. Операции над степенными рядами
Множество степенных рядов образует кольцо относительно операций сложения и умножения, которые мы сейчас определим.
Сложение рядов определяется обычным образом: в ряде г + г', представляющем собой сумму рядов г и г', коэффициент при каждой цепочке есть сумма коэффициентов при соответствующих цепочках в рядах г и г'-.
(г+ г', *> = (r, X) +(г', X).
Умножение рядов определяется, как обычно. Следует только помнить о его некоммутативности: конкатенация сомножителей выполняется в определенном порядке, без перестановок. В произведении рядов г и г', которое обозначается через гг', каждый коэффициент (гг',х) есть сумма всевозможных произведений (гг y)(r'j, z), таких, что yz = х.
Утверждение о том, что множество степенных рядов имеет структуру кольца, предоставляется доказать самому читателю.
Умножение на целое число. Умножение ряда на целое число также определяется обычным способом. В ряде п • г коэффициент при X равен п(г, х).
11.2.3. Топологические понятия
Уточним теперь способ перехода от многочленов к рядам и введем понятие окрестности. Гл. XI. Задание языков с помощью систем уравнений
191
Будем говорить, что ряд г эквивалентен ряду г' по модулю п, и писать
г = г' (mod и),
если (/(*) < п) ф (г, х) = (г', х).
Пусть имеется бесконечная последовательность рядов гі,г2,..., такая, что rn = гп> для всякого п и для всякого п' > п. В этом случае понятно, как определить предел последовательности ги г2, ...: это предел последовательности многочленов, получаемых путем отбрасывания в каждом г„ всех членов, длины которых превосходят /г1).
Теперь ясно, как снабдить кольцо рядов топологией: окрестность некоторого ряда будет представлять собой множество всех рядов, эквивалентных ему по некоторому модулю.
11.2.4. Ряды с неотрицательными коэффициентами
Ряды с неотрицательными коэффициентами («положительные ряды») образуют полукольцо. Кроме того, их опорные множества обладают следующими важными свойствами.
Сложение. Коэффициент (г + г', х), представляющий собой сумму двух неотрицательных целых чисел, отличен от нуля тогда и только тогда, когда хотя бы одно из этих чисел не равно нулю.
Для положительных рядов опорное множество суммы равно объединению опорных множеств слагаемых.
Умножение. Если опорное множество ряда г содержит цепочку у, а опорное множество ряда г' — цепочку г, то опорное множество ряда гг' содержит цепочку yz (поскольку аннулирование членов невозможно). Обратно, если опорное множество ряда гґ содержит цепочку X, то существует хотя бы одна пара (у, z), где у и Z принадлежат опорным множествам рядов г я Ґ соответственно, такая, что yz = х.
Следовательно,
для положительных рядов опорное множество произведения равно произведению (в смысле умножения языков) опорных множеств.
11.2.5. Положительные ряды и КС-грамматики
Читатель, вероятно, уже заметил, что ряды с целыми неотрицательными коэффициентами позволяют дать простое описание выкладок, к которым мы прибегали, строя и решая систему уравнений, связанную с данной КС-грамматикой.
Будем теперь считать, что переменные ?, Я, 33, ... представляют не языки в теоретико-множественном смысле, а формальные
') Заметим, что в этой последовательности каждый следующий член есть продолжение предыдущего. 192
Часть II. Некоторые замечательные классы языков
ряды. Каждому ряду отвечает свое опорное множество, являющееся языком, а также коэффициенты, характеризующие принадлежность цепочки языку и степень ее неоднозначности: О — данная цепочка не порождается, 1—данная цепочка порождается одним способом, 2 — данная цепочка порождается двумя разными способами и т. д.
Система уравнений, сопоставленная данной КС-грамматике, записывается по-прежнему в виде
2=/(2, 21, », ...), И-?(Й, 21, », ...), » = A(8, 21, », ...),
