Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 110

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 136 >> Следующая

*) Пример из романа В. Дудинцева «Не хлебом единым». Эти слова вложены автором в уста одного из эпизодических персонажей — доктора наук Тепикина, и их оказывается достаточно для портрета малограмотного «научного» карьериста.
**) Как и другие отступления от «абсолютной правильности», встречающиеся в художественной литературе.
304 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П. I
и т. п. Ср. выделение слова новая во фразе из стихотво-рения М. И. Цветаевой
Новая найдется дура - Зерить в Волчью седану
или впечатление непринужденности, «разговорности», создаваемое непроективностями в басне И. А. Крылова:
Какой-то по5ар, грамотей,
С поВарни побежал сЗоей
V
В набан; он набожных был праВил^
§ П1.3. Связь между системами составляющих и деревьями подчинения
Пусть С — система составляющих цепочки х й (X; —*?) — дерево подчинения для той же цепочки. Будем говорить, что система С и дерево (X; ->) (или система С и отношение —*?) согласованы, если: 1) группы зависимости всех узлов дерева (Х\ ->) являются составляющими системы С; 2) каждая составляющая системы С является группой зависимости или усеченной группой зависимости некоторого узла дерева (Х\ -*).
Пример. Дерево (17) согласовано с системой (4).
Для дальнейшего будет полезно следующее очевидное замечание. Если система составляющих С согласована с деревом {Х\ -*) и А е С — группа зависимости или усеченная группа зависилЛсти точки а, то среди составляющих, непосредственно вложенных в А, та, КО’
§ П1.3] СВЯЗЬ СИСТЕМ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЕВ
305
торая содержит точку а, является для нее усеченной группой зависимости, а остальные являются группами зависимости некоторых точек, подчиненных а.
Ввиду теоремы П1.1 всякое дерево подчинения, согласованное с какой-либо системой составляющих, проективно. С другой стороны, для всякого проективного отношения подчинения существуют согласованные с ним системы составляющих; одной из них будет множество С0, состоящее из всех точек*) цепочки и их групп зависимости. (Всякая точка совпадает со своей группой зависимости, если она является висячим узлом дерева, и с одной из своих усеченных групп зависимости в противном случае; две группы зависимости пересекаются лишь тогда, когда одна из них содержится в другой.) В общем случае согласованная с деревом подчинения система составляющих не единственна; строение множества таких систем рассматривается в упражнениях П1.7—ШЛО.
Перейдем к обратному вопросу — о деревьях подчинения, согласованных с заданной системой составляющих. Здесь оказывается удобнее исходить из понятия иерархизованной системы составляющих.
Введем следующее определение.
Иерархизованная система составляющих (С, С') цепочки х и дерево подчинения (X; -*) для той же цепочки (или {С, С') и отношение -?) связаны, если:
1) множество групп зависимости узлов дерева совпадает с С — С'; 2) все элементы С' являются усеченными группами зависимости узлов дерева.
Очевидно, всякое дерево, связанное с (С, С'), согласовано с С.
Пример. Дерево (17) связано с иерархизованной системой (15).
Лемма П1.2. а) Если С—система составляющих для цепочки х, А е С и Ха — подцепочка х, соответствующая А, то множество СА = {В | В е С & В s А] есть система составляющих для хА.
б) Если в условиях пункта а) С' есть иерархизация системы С, то С'а=С' [} С а есть иерархизация системы Сд.
*) Точнее — одноточечных подмножеств.
306 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П.
в) Если в условиях пункта а) —? есть отношение по чинения для х, согласованное с С, то отношение -> индуцируемое отношением —*? на ха, есть отношение по чинения для Ха, согласованное с СА.
г) Если в условиях пунктов а), б), в) отношение связано с иерархизованной системой (С, С'}, то—* связано с (Са, С'а).
Лемма Ш.З. Пусть (С, С') — иерархизованная с стема составляющих и В0, В1г ..., Вр — все составля щие высоты 1, причем В0<^С', Ви ВрфС'. ЕЬя при этом (X; -») — дерево подчинения, связанное с (С, С' то (X; —>) получается из объединения деревьев (Во;
(fill (ВР-, ->Вр) добавлением дуг (а0, а,), (а0) а
где а0, аь ..ар — корни деревьев (Во; (Вi; .
(Вр; ~+вр) соответственно.
Доказательства лемм Ш. 2 и Ш. 3 очевидны.
Теорема П1.2. а) Для всякой иерархизованно системы составляющих существует единственное связан ное с ней дерево подчинения.
б) Для всякого дерева подчинения, согласованног с системой составляющих С, существует единственна иерархизация С' системы С такая, что иерархизова ная система (С, С') связана с данным деревом.
Доказательство, а) Пусть (С, С')—иерарх зованная система составляющих для цепочки х и X множество всех точек цепочки х. Для каждой неточечно составляющей А будем обозначать через а(А) непосре ствено вложенную в А главную составляющую и чер
ЪЛА)...... ЬРа{А) (рА^ 1) — непосредственно вложе
ные в А не главные составляющие. Для каждой соста ляющей Лей определим ее главную точку а (Л следующим образом. Если ранг Л равен нулю, то еди, ственная точка Л будет главной. Если главные точк определены для всех составляющих ранга, меньшего и Л — составляющая ранга п, то главной точкой Л б дет главная точка а (А).
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed