Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
есть циклы, то в деревьях полных выводов найдутся сколь угодно длинные отмеченные пути. Пусть символ Л принадлежит какому-либо циклу указанного графа. Тогда для некоторой цепочки coe(VUW) + найдется (Л, со)-дерево Тi в Г, в которой" из корня идет отмеченный путь в висячий узел, помеченный тем же символом Л. Для п = 2, 3, ... положим Тп = = Sub(7'n_b Т0, Тх), где То — единичное дерево с меткой Л в единственном узле. При достаточно большом п дерево Тп будет содержать сколь угодно длинный отмеченный путь из корня в висячий узел с меткой Л. Поскольку грамматика Г приведенная, найдется дерево полного вывода Т, в котором некоторый узел а имеет метку Л. По предыдущему в полном a-поддереве Т' дерева Т из корня исходит хотя бы один отмеченный путь. Полагая Т'п = Sub(Tn, Т0, Т'), видим, что в Т'п из корня идет отмеченный путь, более длинный, чем в Т„,
ДОМЙНАЦИОННЫЁ ГРАММАТИКИ
205
уже в узел, помеченный основным символом; но ввиду приведенности Г дерево Т'п можно «достроить» до дерева полного вывода.
Из лемм 6.1 и 6.2 и из того очевидного обстоятельства, что свойство ограниченности ширины сохраняется при сильной эквивалентности, немедленно вытекает
Теорема 6.5. а) Для всякой Д-грамматики ограниченной ширины можно построить сильно эквивалентную ей простую Д-грамматику. б) Если для Д-грамматики G существует сильно эквивалентная ей простая Д-грамматика, то G имеет ограниченную ширину.
Посмотрим теперь, для каких Б-грамматик существуют эквивалентные в том или ином смысле простые Д-грамматики, или, что то же самое, Д-грамматики ограниченной ширины.
Ясно, прежде всего, что удлиняющая Б-грамматика тогда и только тогда вкладывается в простую Д-грамматику (и притом эффективно*)), когда правая часть каждого ее правила содержит вхождения основных символов. Поэтому из теоремы 6.2 следует, что для всякой Б-грамматики можно построить слабо эквивалентную ей простую Д-грамматику.
Чтобы исследовать вопрос о сильной эквивалентности, введем следующее понятие.
Пусть Г = (F, W,I, R\— Б-грамматика. Будем сопоставлять символам из V U W числа, которые назовем их степенями, следующим образом: (i) степени основных символов, и только их, равны нулю; (ii) пусть для
каждого k — 0.......п — 1 определено понятие символа
степени й; тогда символу А приписывается степень п, если ему не приписано в качестве степени ни одно из чисел 0, ..., п—1 и правая часть каждого правила с левой частью А содержит хотя бы одно вхождение символа степени, не превосходящей п—1. Символы, которым с помощью такой процедуры никакая степень не приписывается, считаем имеющими бесконечную степень. Наибольшая из степеней символов полного словаря Г будет называться степенью грамматики Г.
*) То есть Для Б-грамматики Г можно построить простую Д-грамматику вида (Г,/).
206 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
Ясно, что степень каждого символа, а значит, и степень грамматики можно найти эффективно. Так, грамматики со схемами
{/ ->? Cl, 1 -> aCb, I^-ab, С -> aCb,C -> ab},
{I^CI, 1-+аСЬ,1^аЬ,С^АСВ, С^аЬ,
C^-aabb, А->аа, B->bb} и
{I^IhI^aIb,I^ab}
имеют соответственно степени 2, 3 и оо (хотя все они эквивалентны).
Легко заметить (ср. доказательство теоремы 6.2), что если Г — приведенная удлиняющая Б-грамматика, то ее степень равна точной верхней границе степеней систем составляющих, отвечающих деревьям полных выводов в Г. Поэтому, если назвать Б-грамматики Ti и Гг сильно эквивалентными в случае, когда они эквивалентны и множества систем составляющих, отвечающих деревьям полных выводов в Г] и Г2, совпадают, то будет справедлива
Лемма 6.3. Если две приведенные удлиняющие Ъ-грамматики сильно эквивалентны, то их степени равны.
Нам понадобится также
Лемма 6.4. Для всякой Ъ-грамматики конечной степени можно построить сильно эквивалентную ей удлиняющую Ъ-грамматику конечной степени.
Доказательство, весьма простое, предоставляется читателю (ср. доказательство леммы 4.1 и упражнение 4.1).
Связь понятия степени с Д-грамматиками видна из следующей леммы.
Лемма 6.5. Приведенная удлиняющая Ъ-грамматика тогда и только тогда вкладывается в JX-грамматику без циклов (и притом эффективно), когда ее степень конечна.
Доказательство, а) Пусть степень Б-грамматики Г конечна, А —? ю — произвольное правило Г и степень А равна п. Объявим отмеченными все вхождения в ш символов степеней, не превосходящих п—1. Ясно, что полученная так Д-грамматика не будет иметь циклов, б) Если Д-грамматика ({V,W,I,R),fj не имеет циклов и наибольшая длина пути в графе (FUU?;$!)
СИСТЕМЫ УРАВНЕНИЙ, В ЯЗЫКАХ
207
равна h, то степень каждого символа ае V U W не превосходит наибольшей длины ha пути в графе (VUW; 52), исходящего из узла с меткой а (доказывается очевидной индукцией по ha). Поэтому степень грамматики (V,W,I,R) не превосходит h.
Из лемм 6.1, 6.3, 6.4, 6.5 непосредственно вытекает
Теорема 6.6. а) Для всякой Ъ-грамматики конечной степени можно построить сильно эквивалентную ей простую Л-грамматику. б) Если для приведенной удлиняющей Ъ-грамматики Г существует сильно эквивалентная ей простая Д-грамматика, то степень Г конечна.
