Гладкий - Формальные грамматики и языки - 1973 (947381), страница 18
Текст из файла (страница 18)
Пусть (7 = во ° ° ., в~ = х)— полный вывод в Г и [х[ = и, Непосредственной индукцней по 1 легко показать, что для любого 1 = О, ..., и в грамматике Г' из цепочки !Ек-л выводима цепочка Е" ~ "с~' в,Е '; при этом имитация применения одного правила ф- ф ен )г состоит в применении соответствующего правила из Й' с предварительной «подгонкой» нужного числа символов Е к месту применения правила, если ф[((ф[, или последующим сдвигом вновь полученных в конец цепочки, если [ф['= )ф[; такнлз образом, на имитацию одного шага в Г тратится не более 1+пй шагов в Г', где й = шах ~1 ф | — ~ ф ~1.
В частности, из ч-»е я 1Е"-' выводима не более чем за 1(1 + пд) шагов цепочка х, а поскольку 1Е -' выводима из 1, за п шагов и и ( р1 (р — постоянная), цепочка х выводима в Г' из Iз не более чем за и+1(1+ пй) (1(р+ 1+ рГй) =- гз(р+ 1+ рй) шагов. В то же время очевидно, что всякая цепочка в словаре з', выводимая в Г' из Тв выводима в Г из Е Итак, Г' эквивалентна Г, и Тг (и)-=4р+ 1+ рй) ' [Тг(п)Р 3 а м е ч а н и е. Неизвестно, можно ли в теореме 3.5 заменить квадратичную функцию какой-либо медленнее растущей.
Теорем а 3.6. Для любой неукоричивающей грамматики Г и любого положительного действительного числа с можно построить НС-грамматику Г, эквивалентную Г и такую, что Тг(п)(шах(1, сТг(п)). Д о к а з а т е л ь с т в о. Обратившись к конструкциям, примененным для доказательства леммы 2.4 (о сцеплении) и теорем 2.1 (о сжатии выводов) и 2.2 (об ускорении выводов), мы без труда убедимся, что каждая из этих конструкций, будучи применена к неукорачивающей грамматике, приводит снова к неукорачивающей грамматике. Это дает нам возможность поступить следующим образом.
Пусть à — данная неукорачивающая грамматика и с ) Π— данное действительное число. Фиксируем еще два положительных действительных числа с, и см пока произвольные. Применив конструкцию теоремы об ускорении выводов, построим неукорачивающую грамматику Гь эквивалентную Г и такую, что Тг,(п) .. (~шах(1, с,Тг(п)).
Кэтой грамматике применим конструкцию теоремы о сжатии выводов, причем в качестве постоянной с, фигурирующей в формулировке этой теоремы, возьмем число сз. Полученная при этом грамматика Гз эквивалентна Г, и обладает следующими двумя свойствами: а) Тг,(п)- Тг,(п)+ шах(с,п, 1); б) длйны левых частей правил 1 и д грамматики Гз (см. доказательство теоремы о сжатии) не превосходят двух, а правых — трех.
К Гз применим теперь конструкцию леммы о сцеплении со следующими видоизменениями: правила 3-го и ГРАММАТИКИ СОСТАВЛЯЮЩИХ 3 331 О[шнкА ВРеменнОЙ слОжнОсти нс.языкОВ яз [ГЛ. 3 4-го рода будут определяться иначе, а именно: правила 3-го рода будут иметь вид и(в) — ы, где ы — произвольная непустая цепочка длины, не большей 21, в основном словаре ГВ (! имеет тот же смысл, что и в доказательстве теоремы о сжатии), а правила 4-го рода — вид (и(ьг) ) 0а- Вга, где ы — произвольная цепочка длинй, не большей 21, в основном словаре Г3 и а — произвольный основной символ Г3, кроме того, правилам й грамматики Г3 не будут сопоставляться правила 1-го рода.
Полученную так грамматику мы обозначим ГЗ. Если ! — длина вывода в Г3, т — длина соответствующего вывода в Г3 и ть тм т3, т4 имеют такой же смысл, как в доказательстве леммы о сцеплении, то, рассугкдая, как вэтом доказательстве, мы получаем т3 -'(3+1)т[ —— = 4тг ( 4! (поскольку длины правых частей тех правил Г2, которым сопоставляются правила !-го рода, не превосходят трех, а разности длин левых и правых частей этих правил — единицы; кроме того, ! = т[+ т3+ т[). Отсюда т ( 50 Таким образом, Тг,(п) (5ТГ,(п).
При этом каждое правило 1-го рода грамматики Г3 имеет один из следующих шести видов: (1) й у[ (й) Ф[ — у,у,', «1«2 У [У2' (!ч) Ф -. угу3 (ч) йА0- у Ф' «[52 уг у2у3' Построим теперь по грамматике ГЗ НС-грамматику Г4 следующим образом: а) Каждое правило 1-го рода вида (ш) — (ч!) и каждое правило 2-го рода заменим некоторой системой новых правил, которую мы выпишем только для случая правил 1-го рода вида (ч) и (ч[) (для остальных случаев система строится совершенно аналогично).
Для правила вида (ч): 5[52- РР2; Р530 — «Ру2у3' РуОу0 «у уеу0 Для правила Вида (ч[) РВОЯР «(!ОР АРОР «С[Р. Г[Р «Оу0у0. Оу0у0 «у у0у0 Здесь Р Сг новые символы, разные для разных правил, которые мы присоединяем к вспомогательному словарю грамматики. б) Правила 1-го рода вида (1) и (й), а также правила 3-[о и 4-го рода переносятся в схему Г3 без изменения. Грамматика Г, эквивалентна Г3, поскольку, с одной стороны, применение каждого правила Г3 можно заменить применением соответствующей системы правил Го с другой — в каждом полном выводе в Г, правила одной системы могут применяться только подряд (ввиду того, что цепочка, входящая в полный вывод в ГЗ, не может содержагь более одного вхождения символа вида у), и поэтому вместо каждой такой системы можно применить соответствующее ей правило грамматики Г3.
Очевидно также, что Тг,(п) (4ТГ,(п). Итак, мы имеем Тг,(п) ( 20 (Тг,(п) + [пах (с,п, 1)). 1 Если положить с = †, гда [([ — максимум разно[[[+ 1 ' стей длин правых и левых частей Г, (0([ эффективно определяемо по Г и с,), то в силу последнего из неравенств (2) З 2.! будет с п(ТГ,(п), так что Тг(п)(40ТГ,(п)( (40[пах(1, с Тг(п)). Положив с, = с/40, получим Тг (и)( -- шах(40, сТГ(п)). Остается добавить к схеме Г, всевозможные правила вида 1- х, где Т вЂ” начальный символ Г „ х ~ 3'. (Г4) и ! х !~ (40[14+ 1 (0(4 — максимум разностей длин правых и левых частей правил Г4); поскольку среди таких цепочек содержатся все выводимые в Г, не более чем за 40 шагов, имеем для полученной таким образом НС-грамматики Г': Тг(п)(~шах(1, сТг(п)).
3 ам еча н не. Из теоремы 3.6 вытекает, что в теореме 3.5 квантор существования по Г можно заменить квантором общности. В заключение заметим, что операторы левой и правой глубины, разброса и активной емкости (точнее, соответствующие относительные операторы) являются для класса неукорачнвающих грамматик сигнализирующими и соответствующие сигнализирующие функции для любой неукорачивающей грамматики рекурсивны. (Это частный случай утверждения упражнения 2.!О, б).) й 3.4.
Оценка временной сложности некоторых НС-языков Как отмечалось в предыдущем параграфе„временнйя сложность любой НС-грамматики заключена между линейной и показательной функциями. Естественно 4 зл1 ОценкА ВРеменнОЙ слОжности нс-языкОВ 9$ ГРАММАТИКИ СОСТАВЛЯЮЩИХ 94 !ГЛ. З возникает вопрос: можно ли усилить эту тривиальную оценку, т. е. найти такую функцию Г(п), растущую медленнее показательной, чтобы имело место равенство 2'~с(НС) =2'(НС) *)? К сожалению, ответить на этот вопрос мы не можем. Мало того, неизвестно даже, верно ли соотношение сс~*(НС)=.У(НС).
Единственный результат, имеющийся пока что в указанном направлении, состоит в том, что ни для какой функции Ь(п), растущей медленнее, чем пз, равенство .Ув(НС)=.У(НС) не имеет места. Доказательство этого и будет основной целью настоящего параграфа. Начнем с введения некоторых вспомогательных понятий. Пусть à — НС-грамматика, 0 = (ве, ..., в„) — вывод в Г такой, что 1ао~ = 1, Т' — какое-либо растянутое дерево вывода Р и М' — множество узлов Т'. Распространим отношение «быть предком» («быть потомком»), определенное на М', на множество подмножеств М', являющихся интервалами цепочек ао, ..., в .
Именно, если О(1 «. 1'( и и (г — интервал цепочки в„мы будем называть предком (г в цепочке вз наибольший непустой интервал этой цепочки, для которого все потомки его точек, являющиеся точками вь принадлежат Я; если же такого интервала нет, то предком в цепочке вз мы будем считать любой пустой интервал е4, включая несобственные интервалы ( —, у) и (6, — ), где у и 6 — соответственно первая и последняя точки е;. Если 1'1 имеет непустого предка в цепочке аь то других предков сг в этой цепочке не существует. Интервал цепочки вь для которого Р является предком в вь будет называться потомком Р в цепочке в,.
Если О -= 1 < 1 «=. и, Р— интервал цепочки в; и Я— множество всех точек вь являющихся потомками точек Р (очевидно, ьг также есть интервал), мы будем называть Р точи ы м п редком () в ве, а сг — точным потомком Р в вь Пусть далее 0=(ео, ..., а„) — вывод в НС-грамматике Г, 0'=(е', ..., в'„,„е„) — некоторый соответствующий 0 размеченный вывод н Т' — некоторое соответствующее Р' растянутое дерево вывода. Если Т' фнк") Имеет смысл ставить вопрос лишь оо уснленнн верхней оненнн — ннжнюю, очевидно, усилить нельзя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
