Гладкий - Формальные грамматики и языки - 1973 (947381), страница 58
Текст из файла (страница 58)
а„ СИСТЕМЫ СОСТАВЛЯЮЩИХ 989 993 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИ!!ЕНИЯ [ ! П.!.!! и а„ ..., а„ вЂ” точки отрезка у, либо 6! ) ... ) ])в р„ ..., 6„ — точки отрезки у. Доказательство. Представим у в виде у =у! ... у»„, где [ув] ~!'", ! = 1, ..., 2п. Каждый от зок у! содержит хотя бы одну точку, являющуюся кон некоторой составляющей ранга, большего или рави 2п.
Среди этих 2п точек найдется либо и левых кон либо и правых — пусть для определенности первое. резок у содержит, таким образом, точки у, (... ( являющиеся левыми концами некоторых составляющ' рангов, ббльших или равных 2п. Обозначим прав концы этих составляющих через 6!, ..., 6 соответ венно. Если все они лежат вне у, то, очевидно, 6 = ... ( 6!, так что последовательность ув, ..., у„, 6„, ' ..., 6! удовлетворяет нужному условию. Если же как либо точка 6; принадлежит у, то составляющая А = [уь6!] Содер!Еится в у целиком; она в свою очер содержит вложенную последовательность составля щих А = [ев,т!!]:О[еьт!»]:э... ~[за»,т!»в], и либо сре' точек зь ..., В»в, либо среди точек ч1„..., !)»„Име ся не менее и попарно различных; если, например, им место пеРвое и пРи этом з,, ( ...
( Еби то последо тельность е!и ..., и,, т!», ..., »!!, является искомой. Важными характеристиками составляющей являют также с т е п е н ь л е в о г о в е т в л е н и я, с т е и е н' правого ветвления и степень гнездов н и я (обозначения: ул(А), у" (А), ф(А)). Степени левого и правого ветвления определяют так; 1. Если А — полная составляющая, то ул(А) =уп(А) =О.!!. Если для составляющей А значен' фУнкций Ул и Уп опРеделены и если Ав, Аь, А» все непосредственно вложенные в А составляющие, з' нумерованные слева направо, то ул(А!)=ул(А)+й — 1; уп(А!)=уп(А)+!'.
Для определения степени гнездования введем предв рительно следующее понятие. Назовем последовател ность составляющ!!х [ам Щ, [аи рв], ..., [и, 6„] гн е дом глубины п, охватыв ающи м составляющ ' [а„, рв], если а»(а!«...а„(р„«...~3!< Степень гнездования составляющей А — это, по опред лению, наибольшая глубина гнезда, охватывающего А..
Наибольшие значения ул(А), у" (А) и ф(А) для А ее С называются соответственно степенью лево. го ветвления, степенью правого ветвления и степенью гнездования системы С и обозначаются ул(С), уп(С), ф (С). Величина ф(С) есть, таким образом, наибольшая глубина гнезда, содержащегося в системе С. Степень гнездования составляющей можно определить также индуктивно следующим образом. Пусть А,, ..., А» — все составляющие, непосредственно вложенные в составляющую А, занумерованные слева на.
право. Будем называть составляющую Ав л е во й, А» — п р а в о й, А„..., А» ! (если й ) 1) — с р е д н ими. Кроме того, полную составляющую будем считать средней. Среди левых и правых составляющих будем различать углубляющие и неуглубляющие, которые определим индуктивно. Именно: если состав. ляющая А средняя, то непосредственно вложенные в нее левая и правая составляющие будут неуглубляющими; если А левая, то непосредственно вложенная в А левая составляющая — неуглубляющая, а непосредственно вложенная в А правая составляющая — углубляющая, когда А неуглубляющая, и неуглубляющая, когда А углубляющая; если А правая, симметрично. Кроме тотого, все средние составляющие считаем углубляющими. Теперь ф(А) определяется так: 1.
Если А — полная, то ф(А) = О. П. Пусть ф(А) определено и В непосредственно вложена в А. Тогда ф(В) = ф(А), если В— неуглубляющая составляющая, и ф(В) = ф(А) + 1. если  — углубляющая составляющая. Эквивалентность двух определений степени гнездования без труда доказывается индукцией по высоте. Назовем далее последовательность составляющих [ав, Щ, [ии р»] ..., [а„, р„] левым (праным) полугнездом глубины и, охватываю щи м составляющую [а, р ], если а» ( а! (...
( а„(бв(... . (й«~м соответственно ав(а»(... (а (р < ... ( 6! ( рв. Наибольшую глубину левого (правого) полугнезда, охватывающего данную составляющую А, обозначим фл(А), соответственно ф" (А). Очевидно, ф(А) < ш(п(фл(А), ф" (А)). !О А. В. Гввдввй 990 системы сОстАВляющих и деРЯВья подчйй1нения 1п 1. 1 П.!Л! системы состдиляющих 991 В то же время непосредственной индукцией по высоте А легко показать, что фл(А)(уп(А), фп(А)-.с ул(А).
По, этому ф (А)(ш(п (ул(А), уп (А)), откуда ф (С) ~ ~ппп (ул (С); уп (С)) Широко известна гипотеза В. Ингве [Ъ'пдуе 1960)„" согласно которой в естественных языках икмеются спе-. циальные механизмы, обеспечивающие огрганнченноств степеней левого ветвления предложений (в т«о время как степени правого ветвления ничем в прннцнапе не огра ничены — ср. хотя бы конструкции типа Даам, который, построил Джек) "). Имеются, однако, языики, для которых это предположение заведомо не под.,тверждается (например, венгерский — см.
[Гладкий — Меельчук 1969, стр. 101)); более того, и в языках, с фактавми которы данная гипотеза на первый взгляд хорошо согласуется„ можно, по-видимому, при более детальном и1сследовании обнаружить конструкции довольно большойй левой глу.' бины, вполЪЕ приемлемые не только граммиатически, но и стилистически (ср., в частности, приводимгые в [Паду- чева 1966) примеры для русского языка). Значительно более адекватной характериестикой «синтаксической громоздкости» предложения явлсяется, видимо, степень гнездования. В русском языке, назпример, хотя и можно строить грамматически правил1ьные предложения со сколь угодно большими значегниями ф(С),, но уже очень скоро они начинают воспринеиматься как стилистически недопустимые ввиду их крайняей громоздкости; ср.
хотя бы предложение ( (Прочитавгииий ((полу- 19 84 пенное (ог (опубликовавшего ( (единствениную (после,' а 8 Г 8 9 Иванова) ) монографию) ) ученого) ) письмо) ) брат) (был; 98 ге 54 8;2 110 недоволен), для которого степень гнездованхия равна 5.: 1О См. Об этом, например, [Мартыненко 1971[.[. Построенная для предложения система составляющих указывает в нем словосочетания разньпх «уровней» (составляющие разной высоты), не вводя шри этом ниг какой иерархии среди словосочетаний одновго «уровня».
*) По поводу аргументации, выдвигаемой в полгъау вто11 типо. теаы, см. $7.1. Между тем, в предложении естественного языка часто интуитивно ощущается «главенствование» некоторого словосочетания над другими, в нем не содержащимися. Чтобы в некоторой степени отразить этот факт, можно поступить следующим образом. Пусть С вЂ” система составляющих цепочки х.
Для каждой неточечной составляющей А ~ С выделим в множестве всех составляющих, непосредственно вложенных в А, какую-либо одну составляющую А', которую будем называть г л а вной. Множество всех главных составляющих обозначим С' и назовем пер архивацией системы С. Упорядоченную пару (С, С') назовем пер архизованн ойй с и с те мой составляю щи х. Например, система (4) предложения (3) может быть иерархизована следующим образом (именно такую нерархизацию можно считать интуитивно естественнОй): (15) (Онегин, (добрый (мой приятель))), (родился (на (брегах Иевьс))).
(Главные составляющие здесь подчеркнуты.) Вообще говоря, «естественная» система составляющих может допускать более одной «естественной» иерархизации. Например, в системе (16) Студенты встретили (больного (врача Иванова)) можно взять в качестве главной составляющей (внутри составляющей больного врача Иванова) либо больного, либо врача Иванова; прн первом выборе естественно считать, что речь идет о «больном врача Иванова», во втором — о «больном враче Иванове». При описании предложения естественного языка с помощью системы составляющих часто используется еще один способ введения в эту систему дополнительной информации: рассматривается ее отображение в множество всех подмножеств некоторого конечного множества, элементы которого называются метка ми и содержательно интерпретируются как символы «синтаксических классов» слов и словосочетаний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
