Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Мы рассмотрим теперь один специальный класс Д-грамматик, представляющий особый интерес (в частности, для приложений), .
202 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ (ГЛ. 6
Будем называть Д-грамматику простой*), если во всех ее правилах отмечены только вхождения основных символов.
Если Д-грамматика (Г, f) простая, то во всех строящихся с ее помощью иерархизованных системах составляющих главными составляющими могут быть только точечные. Для случая, когда Г — приведенная грамматика, справедливо и обратное.
Понятие простой Д-грамматики естественно обобщается следующим образом. Пусть Г= ((У, W, /, R), f) — Д-грамматика. Введем на множестве V U W бинарное отношение № следующим образом: а$?Р означает, что в некотором правиле Г с левой частью а правая часть содержит отмеченное вхождение р. Если граф (У U W; &) не содержит циклов (замкнутых путей ненулевой длины), будем называть G Д-гр а м м а т и ко й без циклов.
Лемма 6.1. Для всякой JX-грамматики без циклов можно построить сильно эквивалентную ей простую JX-грамматику.
Доказательство. Пусть h — наибольшая длина пути в графе (VU W; Ж) для данной Д-грамматики G = (Г, /), где Г = (V, W, /, R). Б-грамматику Г мы можем считать приведенной. (Действительно, если Г' = = {V,W',1,R')—грамматика, соответствующая Г по лемме 4.8, и /'— функция, которую f индуцирует на R', то Д-грамматика (Г', f) сильно эквивалентна G, а ее граф (V U W'\ $.') является подграфом исходного графа (У U W\&).) Поэтому при h = 1 грамматика G простая. Пусть h >4 и утверждение доказано для всех h' < h. Назовем рангом вспомогательного символа А наибольшую длину пути в графе (VUW; Ж) с началом Л. Ясно, что правые части правил Г, имеющих левыми частями символы ранга 1, являются цепочками в V. Заме-' ним теперь каждое правило, содержащее в правой части вхождения символов ранга 1, правилом, получающимся из данного путем замены всех вхождений символов ранга 1 в правую часть вхождениями цепочек в V, непосредственно выводимых из этих символов.
*) В литературе для простых Д-грамматик часто используется термин «грамматики зависимостей» • (англ. dependence grammars).
§ G.3J
ДОМИНАЦИОННЫЕ ГРАММАТИКИ
203
Функцию f переопределим на новых правилах так, чтобы для каждого такого правила отмеченными вхождениями были, во-первых, те, которые были таковыми в старом правиле и не были заменены при переходе к новому, и, во-вторых, те, которые возникают из отмеченных вхождений символов в правые части правил вида А —*х, яе V+, при подстановке х вместо отмеченного вхождения А в правую часть старого правила. Построенная таким образом новая Д-грамматика будет, очевидно, сильно эквивалентна G, и в то же время каждый максимальный путь в графе (V U W; Ж) при переходе к новой грамматике укорачивается на единицу; остается воспользоваться индуктивным предположением.
Будем далее называть Д-грамматику G = (Г, f) Д-гр а м м а т и ко й ограниченной ширины, если существует такое число k, что ширина дерева подчинения, сопоставляемого грамматикой G цепочке из ?(Г), не может превосходить этого к. Наименьшее из таких чисел будет называться шириной грамма-т и к и G.
Лемма 6.2. а) Если G = (Г, f) — JX-грамматика без циклов, T = (V,W,I,R) и наибольшая длина пути в графе (V \JW\ Ж) равна h, то G есть грамматика ограниченной ширины, и ширина ее не превосходит h-(g—1), где g — максимум длин правых частей правил Г. (В частности, ширина простой JX-грамматики не превосходит g— 1.)
б) Если Г — приведенная Ъ-грамматика и G —
— (Г, f) — JX-грамматика ограниченной ширины, то G не имеет циклов.
в) Если в условиях пункта а) грамматика Г приведенная, то ширина G не меньше h.
Доказательство. Назовем путь в дереве полного вывода в Г отмеченным, если все его узлы, кроме, быть может, начального, отмечены. Для дальнейшего заметим, что в произвольном дереве полного вывода из любого узла идет хотя бы один отмеченный путь в висячий узел. Пусть а0, ..., ап — отмеченный путь в дереве полного вывода, причем узел а„ висячий, и Д0.....Ап — соответствующая последовательность со-
ставляющих. Вспоминая указанный в доказательстве теоремы П1.2 способ построения дерева подчинения,
204 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ (ГЛ. 6
связанного с данной иерархизованной системой составляющих, мы видим, что если при какой-то иерархиза-ции все составляющие Ль ..., Ап окажутся главными, а Л0 — не главной, то узлу соответствующего дерева подчинения, являющемуся главной точкой Л0, будут подчинены все узлы, являющиеся главными точками не главных составляющих, непосредственно вложенных в Л0> Ль ..., Лп-ь и только они. Но число таких узлов не меньше л и не больше n-(g—1). Если G — грамматика без циклов и наибольшая длина пути в графе
(У U есть h, то длина отмеченного пути в дереве
вывода не может быть больше h, и, следовательно, никакой узел дерева подчинения не может подчинять более h-(g—1) узлов. (Вспомним, что всякая точка цепочки главная для некоторой не главной составляющей.) В то же время из самого определения отношения 91 следует, что хотя бы в одном дереве вывода должен быть хотя бы один отмеченный путь длины h, идущий в висячий узел; а если грамматика Г приведенная, то любое дерево вывода можно вложить в дерево полного вывода, так что, по предыдущему, в некотором дереве подчинения, сопоставляемом какой-либо цепочке грамматикой G, найдется узел, подчиняющий не менее h узлов. Теперь нам достаточно показать, что если Г — приведенная Б-грамматика и в графе (V [) W; Ж)
