Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Дерево называется бинарным, если ширина куста -каждого его невисячего узла равна двум.
Высотой, рангом и степенью узла дерева на-: зываются соответственно длина пути из корня в данный узел, наибольшая длина пути из данного узла в висячий и наименьшая длина пути из данного узла в висячий.* Наибольшее значение высоты узла дерева (совпадающее, очевидно, с наибольшим значением ранга и с ран-
*) Этот термин обычен в лингвистических работах и часто встречается в работах по математической лингвистике. В теории графов более принят термин вершина; мы избегаем его потому, что войн огих математико-лингвистических работах «вершиной дерева» называют корень (ем. ниже). ........
ЦЕПОЧКИ и языки
19
гом корня) называется высотой дерева. Наибольшее значение степени узла дерева называется сте-пенью дерева.
Дерево, состоящее из одного лишь корня, называется единичным.
Множество М с заданными на нем двумя бинарными отношениями R{ и R2 называется биграфом (и обозначается (М; Ru R2)). Нагруженным биграфом называется упорядоченная система (М; Ru R2, U, g), где {M; Ri, R2) — биграф, U — конечное множество и g — отображение М в U.
Упорядоченная система (М\ R, ф), где М и R — множества и ф — отображение R в множество всевозможных упорядоченных пар элементов М, называется мультиграфом. Элементы М называются узлами мультиграфа, элементы R — его дугами. Если (а, Ь) = = ф(а), говорим, что дуга а идет из а в Ь\ а есть начало а; b есть конец а. Путь в мультиграфе определяется так же, как в графе. (Граф можно было бы определить как мультиграф с разнозначным ф.)
§ 1.1. Цепочки и языки
Мы будем рассматривать непустое конечное множество V, которое будем называть словарем (или ал-фавитом), а его элементы — элементарными символами (или просто символами, а также буквами). Произвольную конечную последовательность элементов V, т. е. отображение в V некоторого (конечного) начального отрезка натурального ряда, будем называть цепочкой*) в словаре V. Отображаемый отрезок натурального ряда может быть и пустым; тогда мы говорим о пустой цепочке. Непустую цепочку мы, как правило, будем записывать в виде ы = Ь\ ... Ьп, где bi — образ числа i. Пустую цепочку будем обозначать символом Л. Мощность отображаемого отрезка натурального ряда будет называться длиной цепочки; в частности, длина пустой цепочки равна нулю. Длина Цепочки (о обозначается ] со |.
*) Мы не пользуемся более распространенным в математических работах термином слово во избежание ненужной омонимии в лингвистических приложениях.
2*
20
ОСНОВНЫЕ понятия
[ГЛ.
Например, алкилалкоксисилан — цепочка длины 1 в словаре V, состоящем из 32 русских букв, а такж в словаре V = {а, и, к, л, н, о, с} и в любом словаре, со» держащем V'. Иногда мы будем изображать цепочку
bi Ь* Ьп_, ъп
-----1------:---!---------1—
Рис. 1.
by ... Ьп на отрезке горизонтальной прямой так, как по казано на рис. 1. - :
Множество всех цепочек в словаре V будет обозна-' чаться через V*, множество всех непустых цепочек в V — через V+.
Конкатенацией (или результатом конкатенации), непустых цепочек Ь{ ... Ьп и С\ ... cv называется цепочка di ... dn+p, где di = bu ..., dn = bn, dn+1 = = сi, , dn+p = cp. Кроме того, конкатенация цепочек ш и А, равно как и А и со, где ш — произвольная цепочка, считается по определению равной со. Конкатенацию цепочек со и ф мы будем обозначать соср.
Заметим, что слово «конкатенация» обозначает у нас и операцию и ее результат. Иногда эту операцию называют также умножением, а ее результат — произведением цепочек.
Операция конкатенации, очевидно, ассоциативна, но не коммутативна *).
Вместо шоа ... со мы будем обычно писать ш"; ш1
п раз
будет означать и; со0 будет означать А.
Если ы = qnj), мы будем называть ф началом о» и if концом со. В частности, всякая цепочка есть начало и конец самой себя.
Мы введем также две частичные операции, обратные для конкатенации: левое деление и правое деление. Именно, левым (правым) частным от деления цепочки со на цепочку ф называется цепочка г|з такая, что ф^ = со (соответственно \|хр = (й). Левое частное от деления со на ф будет обозначаться через ф\ы, правое — через со/ф-
*) За исключением случая, когда V состоит из одного элемента.
ЦЕПОЧКИ и языки
21
Например, цепочка рококо есть конкатенация цепочек рок и око, цепочка окорок — конкатенация цепочек око и рок; рок—око\окорок=рококо/око-, око=рок\ \рококо=окорок/рок\ частных рок\окорок, око\ \рококо, окорок/око, рококо/рок не существует.
Если для каких-либо цепочек со, <р, r|i, г)2 в словаре У имеет место равенство со = т)1фг]2, мы будем называть цепочку г|1*ф*г]2, где символ * не принадлежит V, вхождением цепочки <р в цепочку со. Если существует вхождение ф в со, мы будем называть ф л од цепочкой со. В случае, когда длина цепочки ф равна 1, т. е. ф состоит из одного символа Ь, будем говорить
о вхождении символа 6 в цепочку со. Вхождения символов в цепочку мы нередко будем называть ее точ-к а м и.
Число вхождений символа а в цепочку со будет обозначаться | CO j а •
Если а = г)1*й*г)2И P = — точки одной и
