Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ ri.1.11
СЙСТЁМЫ СОСТАВЛЯЮЩИХ
287
Нетрудно видеть (упражнение П1.3), что граф (С; является деревом, корнем которого служит
полная составляющая и висячими узлами — точечные составляющие. Это дерево называется деревом составляющих; его графическое изображение может служить еще одним наглядным способом записи системы составляющих. Например, система составляющих
(4) предложения (3) представляется следующим деревом:
Онегин, добрый мой приятель, родился на брегах Невы
Рассматривая составляющую как узел дерева составляющих, мы можем определить ее высоту, ранг и степень, как на стр. 18. Вместо «ширина (высота, степень) дерева (С; будем говорить «ширина
(высота, степень) системы С».
Систему составляющих, имеющую бинарное дерево, мы также будем называть бинарной.
Заметим, что если ширина системы С равна I, то длина составляющей ранга г не превосходит Г. Поэтому каждый отрезок цепочки, длина которого больше или равна Г, содержит точку, являющуюся левым или правым концом какой-либо составляющей ранга, не меньшего г.
При изучении систем составляющих, связанных с грамматиками, оказывается полезной следующая
Лемма П1.1. Пусть С — система составляющих Цепочки xyz, I — ширина С и | у \ ^ 2п • 12п. Тогда найдутся точки ... ^ а„ < ^ ... цепочки xyz
такие, что [а,, р,].[а„, Р„]еС и либо а, < ... < ап
Онегин, добрый мой приятель
Ф
родился на брегах Невы
Онегин добрый мой приятель
родился на брегах Невы
4- I
на брегах Невы
4- 4-
мой приятель
Ф I
брегах Невы
288 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [
и аь ап — точки отрезка у, либо Р, > ... > Р„ р!, ..., р„ — точки отрезка у. ?
Доказательство. Представим у в виде у = г/1 ... г/г™, где \уг\^12п, i = 1, ..., 2га. Каждый от зок г/i содержит хотя бы одну точку, являющуюся кон некоторой составляющей ранга, большего или равн 2п. Среди этих 2га точек найдется либо га левых кон либо п правых — пусть для определенности первое, резок у содержит, таким образом, точки yi < • • • < являющиеся левыми концами некоторых составляющ рангов, больших или равных 2га. Обозначим прав концы этих составляющих через 6ь ..., бп соответ венно. Если все они лежат вне у, то, очевидно, 8п ^
... sg; 61, так что последовательность уь • • •, \п, бп,
..., 6i удовлетворяет нужному условию. Если же как либо точка Si принадлежит у, то составляющая А = [yj, Sj] содержится в у целиком; она в свою очер содержит вложенную последовательность составля щих А = [еь Tji] [е2, т)г] ^ [е2п, т]2г1], и либо ср'е'
точек 8i, ..., е2п, либо среди точек rji, ..., r\in име, ся не менее п попарно различных; если, например, им место первое и при этом ег, < ... < sin, то последо тельность ..., е1п, ..., является искомой. -
Важными характеристиками составляющей являют, также степень левого ветвления, степей; правого ветвления и степень гнездов; ния (обозначения: ул(А), г/п(Л), ф(Л)).
Степени левого и правого ветвления определяют так: I. Если А — полная составляющая, то ул(А) = уп(А) =0. II. Если для составляющей А значен' функций ул и г/п определены и если А0, Аи ..., Ak все непосредственно вложенные в А составляющие, з; нумерованные слева направо, то
г/л(Лг) = г/л(Л) + ? — г; yn(At) = г/п(Л) + г.
Для определения степени гнездования введем предв рительно следующее понятие. Назовем последовател ность составляющих [ао, Ро], [cti, pj, ..., [а„, рп] гне дом глубины га, охватывающим составляющ ’ [а„, р„], если а0 < «1 < • • • < а„ < р„ < ... < Pi < Степень гнездования составляющей А — это, по опред лению, наибольшая глубина гнезда, охватывающего А. ,
§ П.1.1]
СИСТЕМЫ СОСТАВЛЯЮЩИХ
289
Наибольшие значения г/л(Л), уи{А) и ф(Л) для /1еС называются соответственно степенью лево* го ветвления, степенью правого ветвления и степенью гнездования системы С и обозначаются ул(С), уп(С), ф(С). Величина ф(С) есть, таким образом, наибольшая глубина гнезда, содержащегося в системе С.
Степень гнездования составляющей можно определить также индуктивно следующим образом. Пусть Ло, ..., Ak — все составляющие, непосредственно вложенные в составляющую Л, занумерованные слева направо. Будем называть составляющую Л0 левой, Аи — п р а в о й, Аи ..., Ah-i (если 1) — средни-м и. Кроме того, полную составляющую будем считать средней. Среди левых и правых составляющих будем различать углубляющие и неуглубляющие, которые определим индуктивно. Именно: если состав-* ляющая Л средняя, то непосредственно вложенные в нее левая и правая составляющие будут неуглубляющими; если Л левая, то непосредственно вложенная в Л левая составляющая — неуглубляющая, а непосредственно вложенная в Л правая составляющая — углубляющая, когда Л неуглубляющая, и неуглубляющая, когда А углубляющая; если Л правая, симметрично. Кроме то-того, все средние составляющие считаем углубляющими. Теперь ф(Л) определяется так: I. Если Л — полная, то ф(Л) =0. II. Пусть ф(Л) определено и В непосредственно вложена в Л. Тогда ф(?) — ф(Л), если В— неуглубляющая составляющая, и ф(5) = ф(Л) + 1, если В — углубляющая составляющая. Эквивалентность двух определений степени гнездования без труда доказывается индукцией по высоте.
