Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Заметим, что каждая точка а цепочки х будет гла ной для одной и только одной не главной составляюще Действительно, если Л—точечная составляющая, с стоящая из единственной точки а, Л0, Ль ..., Аи~А путь в дереве составляющих из его корня (полной с
§[113) СВЯЗЬ СИСТЕМ СОСТАВЛЯЮЩИХ И-ДЕРЕВЬЕВ. 307
ставляющей) в Л и последняя на этом пути не главная составляющая есть Лг„ (О^г'о^й), то Л*0, Л*„+ь •••
..., Ak — в точности все составляющие системы С, для которых а служит главной точкой; поэтому составляющая Л(а будет искомой.
Положим теперь а —* р, если а — главная точка какой-либо составляющей Лир — главная точка одной из составляющих 6, (Л), ..., ЬРа(А). Из только что сделанного замечания немедленно вытекает, что: а) ни в одну точку цепочки х не входит более одной дуги;
б) во всякую точку х, кроме главной точки полной составляющей, входит дуга; в) в графе (Х\ -*) нет замкнутых путей ненулевой длины. Итак, (Х\ -*) — дерево подчинения для х (с корнем в главной точке полной составляющей). Покажем, что это дерево связано с (С, С'). .Для этого достаточно установить следующий факт: для любого г, 0 ^ г ^ R, где R — высота системы С, каждая не главная составляющая ранга г является группой зависимости своей главной точки, а каждая главная составляющая ранга г — усеченной группой зависимости своей главной точки. (Действительно, отсюда, поскольку каждая точка цепочки главная для некоторой не главной составляющей, будет следовать, что С—С' совпадает с множеством групп зависимости.) Докажем это утверждение сначала для г — 0. Пусть Л — точечная составляющая; тогда Л = {а} и а — главная точка -4. Если при этом Л — не главная составляющая, то ни для какой составляющей, отличной от Л, точка а не будет главной, так что (по определению отношения —?) эта точка окажется в дереве (X; ->) висячим узлом и ее группа зависимости будет состоять лишь из нее самой. Если же Л — главная составляющая, то непременно найдутся точки, подчиненные а (такими будут хотя бы главные точки других составляющих, непосредственно вложенных в ту же составляющую, что и Л), так что Л не Может быть группой зависимости точки а и поэтому является ее усеченной группой зависимости. Пусть теперь Утверждение доказано для всех г, меньших го (г о ^ 1),
4 — составляющая ранга г0 и а — ее главная точка. Если В0, Ви • ? •. Вр — все непосредственно вложенные в ^ составляющие и В0 является главной, то по индуктивному предположению В0 есть усеченная группп
308 системы составляющих и Деревья подЧйнёнИя [ft 1
зависимости точки а, а В и ..., Вр — группы зависимо-; сти своих главных точек. Таким образом, А есть объединение усеченной группы зависимости точки а с группами зависимости некоторых точек, подчиненных а, — а тако множество есть либо группа зависимости, либо усечен; ная группа зависимости для а. Если при этом А — главная составляющая, то существуют точки, подчиненны а и лежащие вне А, если же А — не главная составляющая, то таких точек нет (так как а не является тогда-главной точкой ни для какой составляющей, не содержащейся в А). Поэтому в первом случае А — усеченная группа зависимости для а, во втором — группа зависимости.
Единственность дерева, связанного с иерархизованной системой составляющих (С, С/), мы докажем индукцией по высоте г системы С. При г = 0 утверждение тривиально. Пусть оно доказано для всех г <С г0 и С имеет высоту Го. Обозначим через В0, Ви ..., Вр сек ставляющие глубины 1. Пусть (X, -»i) и (X, ->2) —два дерева подчинения, связанных с (С, С'). По лемм
П1.2 для каждого / = 0........р отношение (* =
= 1,2), индуцируемое отношением на Bj, связано иерархизованной системой (Cbj, C'bj)- Отсюда по индук:
тивному предположению следует, что для каждого / = 0, ..., р деревья (fi/, ->1 Bj) и (В/, ->2Ву> совпа'
дают. А это в силу леммы П1. 3 влечет совпадение де ревьев (X, ->i) и (л, ->2)- ;
б) Пусть С — система составляющих, согласованна с некоторым деревом подчинения. Для каждой неточеч: ной составляющей ЛеС, являющейся группой зависи мости или усеченной группой зависимости некоторо точки а, объявим главной ту из непосредственно вло женных в А составляющих, которая содержит а. Пр такой иерархизации в силу замечания, сделанного пос ле определения согласованности (стр.304—305),всегда ные составляющие будут усеченными группами зависи мости, а не главные—группами зависимости; но все груп пы зависимости по условию являются составляющими так что множество не главных составляющих совпадет ' множеством групп зависимости. Единственность нужно иерархизации сразу следует из упомянутого замечания
§ ш.з] связь систем составляющих и Деревьев 309
Итак, для каждой системы составляющих имеется взаимно однозначное соответствие между ее иерархиза-циями и согласованными с ней деревьями подчинения.
Замечания. 1) В рассуждениях этого параграфа проективность нужна только для того, чтобы все группы зависимости были отрезками. Если изменить определение системы составляющих, допустив в качестве ее элементов циклические отрезки или даже произвольные множества точек цепочки (конечно, при сохранении пунктов I, II определения на стр. 282), то все наши рассуждения будут годиться для любых слабо проективных, соответственно вообще для любых, деревьев подчинения.
