Гладкий - Формальные грамматики и языки - 1973 (947381), страница 61
Текст из файла (страница 61)
Здесь оказывается удобнее исходить из понятия иерархизованной системы составляющих. Введем следующее определение. Иерархизованная система составляющих (С, С') цепочки х и дерево подчинения (Х; - ) для той же цепочки (или (С, С') и отношение -».) с в я з а н ы, если: 1) множество групп зависимости узлов дерева совпадает с С вЂ” С', 2) все элементы С' являются усеченными группами зависимости узлов дерева: Очевидно, всякое дерево, связанное с (С, С'), согласовано с С. П р и м е р.
Дерево (17) связано с иерархизованной системой (15). Лемма П1.2. а) Если С вЂ” система составляющих для цепочки х, А ~ С и хл — надцепочка х, соответству!Ои(ая А, то множество Сл = (В) В еи С дс В а А) есть система составляющих для хл. б) Если в условиях пункта а) С' есть иерархизация системы С, то СА=С'Г)Сл есть иерархизация систех!ы С„, ') Точнее — одноточечных подмножеств. 3оа системы состАВляющих и деРеВья пОдчинения 1и.
» пс »1 сВязь систем состАВляющих и деРВВьеВ збт в) Если в условиях пункта а) — есть отношение по чинения для х, согласованное с С, то отношение -+ индуцируемое отношением — на хл, есть отношение по чинения для хл, согласованное с С,с. г) Если в условиях пунктов а), б), в) отношение связано с иерархизованной системой (С, С'), то связано с (Сл, Сл). Лемма П1.3. Пусть (С, С') — иерархизоеанная с стема составляющих и Во, В„..., Вр — зсе составля щие вьссогы 1, причем Во оп С', В„..., ВрФС'. ЕЬя при этом (Х; -+) — дерево подчинения, связанное с (С, С' то (Х; -«) получается из объединения деревьев (Во, -«в, (Вс, -«в,) ..., (Вр„— «в ) добавлением дуг (а„а,), ..., (а,, а где ао, аи ..., ар — корни деревьев (Во, '— в,),(Вс, '-«в,),.
' ..., (Вр, -«в ) соответственно. р Доказательства лемм П1. 2 и П1. 3 очевидны, Т е о р е м а П1. 2. а) Для всякой иерархизованно системы составляющих существует единственное связан ное с ней дерево подчинения. б) Для всякого дерева подчинения, согласованног с системой составляющих С, существует единственна' иерархизация С' системы С такая, что иерархизова ная система (С, С') связана с данным деревом. Доказательство. а) Пусть (С, С) — иерарх зованная система составляющих для цепочки х и Х множество всех точек цепочки х. Для каждой неточечно составляющей А будем обозначать через а(А) непосре ствено вложенную в А главную составляющую и чер Ьс(А), ..., Ьр„(А) (рл~)1) — непосредственно вложе ные в А не главные составляющие.
Для каждой саста ляюшей А ЕЕ В определим ее главную точку а(А следующим образом. Если ранг А равен нулю, то еди ственная точка А будет главной. Если главные точк определены для всех составляющих ранга, меньшего н А — составляющая ранга и, то главной точкой А б дет главная точка а(А). Заметим, что каждая точка а цепочки х будет гла ной для одной и только одной не главной составляюще Действительно, если А — точечная составляющая, с стоящая нз единственной точки а, Аы Аь ..., А»=А путь в дереве составляющих из его корня (полной с ставляющей) в А и последняя на этом пути не главная составляющая есть Ас, (О~(со~(й), то Ас„Ас«+ь ..., А» — в точности все составляющие системы С, для которых а служит главной точкой; поэтому составляющая Ас, будет искомой.
Положим теперь а- р, если а — главная точка какой-либо составляющей А и )) — главная точка одной из составляющих Ь, (А), ..., Ь „(А). Из только что сделанного замечания немедленно вытекает, что: а) ни в одну точку цепочки х не входит более одной дуги; б) во всякую точку х, кроме главной точки полной составляющей, входит дуга; в) в графе (Х; — +) нет замкнутых путей ненулевой длины. Итак, (Х; — ) — дерево подчинения для х (с корнем в главной точке полной составляющей).
Покажем, что это дерево связано с (С, С') ..Для этого достаточно установить следующий факт: для любого г, 0 ( г ( ст', где 11 — высота системы С, каждая не главная составляющая ранга г является группой зависимости своей главной точки, а каждая главная составляющая ранга г — усеченной группой зависимости своей главной точки. (Действительно, отсюда, поскольку каждая точка цепочки главная для некоторой пе главной составляющей, будет следовать, что С вЂ” С' совпадает с множеством групп зависимости.) Докажем зто утверждение сначала для г = О.
Пусть А — точечная составляющая; тогда А = (а) и а — главная точка 4. Если при этом А — не главная составляющая, то ни для какой составляющей, отличной от А, точка а не будет главной, так что (по определению отношения - ) зта точка Окажется в дереве (Х; -+) висячим узлом и ее группа зависимости будет состоять лишь из нее самой. Если же А — главная составляющая, то непременно найаутся точки, подчиненные а (такими будут хотя бы главные точки других составляющих, непосредственно вложенных в ту же составлясошую, что и А), так что А не может быть группой зависимости точки а и поэтому является ее усеченной группой зависимости.
Пусть теперь утверждение доказано для всех г, меньших го (го) 1), 4 — составляющая ранга г, и а — ее главная точка. Если Во, Вь ..., „— все непосредственно вложенные в 4 составляющие и В, является главной, то по индуктивному предположению Во есть усеченная группо збз системы состхвля1ощих и дегевья подчинения ]и 1 » ПЬЗ] СВЯЗЬ СИСТЕМ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЕВ ' Зпй зависимости точки а, а В1, ..., Вр — гРУппы зависимо-: сти своих главных точек.
Таким образом, А есть объединение усеченной группызависимости точки а с группами зависимости некоторых точек, подчиненных а,— а тако множество есть либо группа зависимости, либо усечен ная группа зависимости для а. Если при этом А — главная составляющая, то существуют точки, подчиненны а и лежащие вне А, если же А — не главная составляющая, то таких точек нет (так как а не является тогда главной точкой ни для какой составляющей, не соде~Ъ~ жащейся в А).
Поэтому в первом случае А — усеченная группа зависимости для а, во втором — группа зависимости. Единственность дерева, связанного с иерархизованной системой составляющих (С, С'), мы докажем индукцней по высоте г системы С. При г = 0 утверждение тривиально. Пусть оно доказано для всех «(г«и С имеет высоту г» Обозначим через Во, В1, ..., Вр составляющие глубины 1. Пусть (Х, — 1) и (Х, — ») — два дерева подчинения, связанных с (С, С').
По лемм П1.2 для каждого 1 О, ..., р отношение 1В](1= = 1,2), индуцируемое отношением -+1 на Вь связано иерархизованной системой (СВ, Св ). Отсюда по индук ] ' тинному предположению следует, что для каждого 1 = О, ..., р деревья (В], -»1В ) и (В], -+»В ) совпа дают. А это в силу леммы П1. 3 влечет совпадение де ревьев (Х, -+,) и (Х, а). б) Пусть С вЂ” система составляющих, согласованна' с некоторым деревом подчинения. Для каждой неточеч ной составляющей А ~ С, являющейся группой зависи мости или усеченной группой зависимости некоторо точки а, объявим главной ту из непосредственно вло женных в А составляющих, которая содержит 1».
Пр такпй иерархизации в силу замечания, сделанного пос ле определения согласованности (стр. 304 — 305), все гла ные составляющие будут усеченными группами зависи мости, а не главные — группами зависимости;новсегруп пы зависимости по условию являются составляющими так что множество не главных составляющих совпадет множеством групп зависимости.
Единственность нужно иерархизации сразу следует из упомянутого замечания Итак, для каждой системы составляющих имеется взаимно однозначное соответствие между ее иерархизациями и согласованными с ней деревьями подчинения. 3 а м е ч а н и я. 1) В рассуждениях этого параграфа 'проективность нужна только для того, чтобы все группы зависимости были отрезками. Если изменить определение системы составляющих, допустив в качестве ее элементов циклические отрезки или даже произвольные множества точек цепочки (конечно, при сохранении пунктов 1, П определения на стр. 282), то все наши рассуждения будут годиться для любых слабо проективных, соответственно вообще для любых, деревьев подчинения.
2) Системы составляющих н деревья подчинения характеризуют синтаксическую структуру предложения в разных аспектах. С помощью первых описываются в явном виде словосочетания, но игнорируется ориентация связей (т. е. не различаются «главные» и «зависимые» элементы); вторые дают возможность рассматривать направленные связи, но только между отдельными словами. Между тем во многих случаях было бы естественнее описывать структуру предложения, рассматривая направленные связи не только между словами, но и между словосочетаниями. В какой-то мере здесь могут помочь иерархизованные системы составляющих; однако из теоремы П1.2 видно, что в некотором смысле их возможности не шире, чем у проективных отношений подчинения: с помощью нерархизованных систем составляющих удается описать направленные связи словосочетаний только тогда, когда в каждом словосочетании достаточно естественным образом выделяется «главное слово» так, что ему можно передать пассивную связь словосочетания (т.
е. вместо того, чтобы подчинить какому-то элементу все словосочетание, подчинить тому же элементу главное слово); это означает, что система направленных связей между словосочетаниями, т. е. иерархизованная система составляющих, должна быть содержательно равносильна системе связей между их главными словами, а последняя есть не что иное, как дерево подчинения, связанное с исходной иерархизованной системой. Однако бывают словосочетания, в которых либо вооб ще не удается выделить естественным образом главное 818 системы состдвляющих и деревья подчинения !п.
! УПРАЖНЕНИЯ 8П слово, либо «подвешивание» словосочетания за главное слово не оправдано. Например, в конструкциях с однородными членами нет оснований считать то или иное слово главным; в сложных формах глагола (типа буду читать) естественно считать все их внешние связи относящимися только ко всему словосочетанию как целому, поскольку эти формы синтаксически ведут себя так же, как простые. Сходным образом можно трактовать сочетания модальных глаголов и иных модальных слов с инфинитивами, конструкции, содержащие определенные стандартные лексические функции (Жолковский— Мельчук 1967] (например, Орегь 1псер), и некоторые другие типы конструкций. Именно в таких конструкциях, при попытках описать их с помощью деревьев подчинения часто возникает непроективностьс Пеговы здесь будут играть Нети; до«лада дола ошзыд «омиссия *! Эти и другие случаи содержательной неадекватности деревьев подчинения и систем составляющих привели к попыткам разработать другие, более сложные способы описания синтаксической структуры предложения.
Один из таких способов, являющийся одновременным обобщением систем составляющих и деревьев подчинения, предложен в [Гладкий 1969, 1971!. Останавливаться на этих вопросах подробнее мы не будем, поскольку они не имеют прямого отношения к предмету книги. Упражнения П1.1. Показать, что если в цепочке расставлены каким-либо об. разом левые и правые скобки, то существует не более одного взаимно однозначного отображения множества левых снобок на множество правых, при котором каждая левая скобка расположена левее своего «) Дать Орет~(отзыв). образа и отрезки, ограниченные левыми скобками и соответствующими им правыми, образуют систему составляющих данной цепочки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
