Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 65
Текст из файла (страница 65)
Пусть лано дерево разбора, соответствующее НФХ-грамматике 6=(Р Т Р 5), и пусть кроной дерева является терминальная цепочка и. Если н — наибольшая длина пути (от корня к листьям), то Ц < 2" '. Доказательство. Докажем с помощью простой индукции по н. ' Напомним, что в русскоязычной литературе был принят термин "лемма о разрастании'*, но "накачка", на паш взгляд, точнее отражает суть пронсхоляшсго. — Прим реа 7.2, ЛЕММА О НАКАЧКЕ ДЛЯ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 287 Базис.
и = 1. Напомним, что длина пути есть число ребер, т.е. на 1 меньше числа узлов. Таким образом, дерево с максимальной длиной пути 1 состоит из корня и листа, отмеченного терминалом. Цепочка ж является этим терминалом, и рг~ = 1. Поскольку 2" ' = 2' = 1, базис доказан. Индукция. Предположим, самый длинный путь имеет длину и, и и > 1, Корень де-' рева использует продукцию, которая должна иметь внд А — э ВС, поскольку и > 1, т.е. нельзя начать дерево, использовав продукцию с терминачом. Ни один из путей в поддеревьях с корнями в В и С не может иметь длину больше, чем п — 1, так как в этих путях исключено ребро от корня к сыну, отмеченному В или С. Таким образом, по предположению индукции эти два поддерева имеют кроны длины не более 2" '.
Крона всего дерева представляет собой конкатенацию этих двух крон, поэтому имеет длину не более 2"' — ' 2" ~ = 2" '. Шаг индукции доказан. П 7.2.2. Утверждение леммы о накачке Лемма о накачке для КС-языков подобна лемме о накачке для регулярных языков, но каждая цепочка - КС-языка Е разбивается на пять частей, и совместно накачнваются вто- рая и четвертая из них.
Теорема 7.18. (Лемма о накачке для КС-языков.) Пусть Š— КС-язык. Тогда сушествует такая константа л, что если .— произвольная цепочка из Е, длина которой не меньше и, то можно записать - = игзгху, причем выполняются следуннцие условия. 1. ~гнх~ < и. Таким образом, средняя часть не слишком длинная. 2. иг и А Поскольку г и х — подцепочки, которые должны "накачиваться", это условие гласит, что хотя бы одна из ннх непуста.
3. иг'иху е Е для всех 1> О. Две цепочки, г и х, могут быть "накачаны" произвольное число раз, вкл|очая О, и полученная при этом цепочка также будет принадлежать Е,. Доказательство. Вначшче для Е найдем грамматику С в нормальной форме Хомского. Технически это невозможно, если Е есть КС-язык Я или (к). Однако при Е = О утверждение теоремы, которое говорит о цепочке =, ие может быть нарушено, поскольку такой цепочки я нет в О. НФХ-грамматика О в действительности порождает Š— (к), но это также не имеет значения, поскольку выбирается п > О, и = никак не сможет быть е Итак, пусть НФХ-грамматика О'=(Р, Т, Р, В) имеет и переменных и порождает язык Е(0) = Š— (г). Выберем и = 2 . Предположим, что из Е имеет длину не менее ж По теорел1е 7.17 любое дерево разбора, наибольшая длина путей в котором не превышает е, должно иметь крону ллиной не более 2" ' = и!2.
Такое дерево разбора не может иметь крону =, так как для этого слишком длинная. Таким образом, любое дерево разбора с кроной = имеет пугь длиной не менее гл + 1. ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 288 На рис. 7.5 представлен самый длинный путь в дереве для; где 7» не менее т, и путь имеет длину 7» + 1. Поскольку к > т, на этом пути встречается не менее т ч. 1 переменных Ае, Ан ..., А».
Но )з содержит всего т различных переменных, поэтому хотя бы две из и+1 последних переменных на пути (т.е. от А» до А» включительно) должны совпадать. Пусть А, = А, где»» — т <» < / < 1». Тогда дерево можно разделить так, как показано на рнс. 7.6. Цепочка и является крояой поддерева с корнем А,. Цепочки г и х — зто цепочки соответственно слева и справа от»е в кроне большего поддерева с корнем А,. Заметим, что цепных продукций нет, поэтому т их не могут одновременно быть е, хотя одна из них и может.
Наконец, и и у образуют части ", лежащие соответственно слева и справа от поддерева с корнем А,. Рнс. 7.5. Каждая достаточно длинная цепочка в Е должна ивен»ь длинный путь в своем дереае разбора Если А, = А, = А, то по исходному дереву можно построить новое дерево разбора, как показано на рис. 7.7, а.
Сначала л»ожно заменить поддерево с корнем Аь имеющее крону мех, поддеревом с корнем Ан у которого крона»в. Это допустимо, поскольку корни обоих поддеревьев отмечены одной и той же переменной А. Полученное дерево представлено карис, 7.7, б. Оно имеет крону и соответствует случаю» = 0 в шаблоне цепочек и»7»еху. Еще одна возможность представлена на рис.
7.7, в. Там поддерево с корнем А, заменено поддеревом с корнем А,. Допустимость этой замены также обусловлена тем, что отметки корней совпадают, Кроной этого дерева является иЬех у. Если бы мы затем заменили поддерево с кроной ьч (см, рис, 7.7, в) большим поддеревом с кроной ззех, то получили бы дерево с кроной»»е'их'у и так далее для любого показателя й Итак, в» существуют деревья разбора для всех цепочек вида иг'»вхуз и лемма о накачке почти доказана. Осталось условие 1, гласящее, что ~зпех~ < и.
Мы выбирали А, как можно ближе к крове дерева, поэтому 7»- » < т. Таким образом, самый длинный путь в поддереве с корнем 7.2. ЛЕММА О НАКАЧКЕ ДЛЯ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 289 1, П ме 7.17 поддерево с корнем А, имеет крону, дли- А, имеет длину не более т +, По теореме на которой не больше, чем 2 = и. С2 Ю У Рис. 7.б. Разделение цепочки х для накачивания 7.2.3. Приложения леммы о накачке к КС-языкам , к к и я е лярных языков, исполь- Отметим, что лемма о накачке для КС-языков, как и дл р гу зуется в виде "игры с противником" следующим образом. бо ный. 1. Мы выбираем язык, жел Е, ая доказать, что он не контекстно-сво д 2.
Наш "противник" вы ирает зар б ранее неизвестное нам и, поэтому мы должны рассчи- тывать на любое возможное значение. 3. Мы выбираем г и при этом можем использовать и как параметр. 4. П отивник разбивает - на иизиху, соблюд гр ая о аничения 1изех~ < п и их а е. ротивн 1 е- ыби ая Г и показывая, что ии'зеху не приналл- 5. Мы "выигрываем", если можем, вы ир жит языку А. в, о кото ых с помощью леммы о накачке Р о —,„им несколько примеров языков, о ко р ассмо — „ н . ", тя можно доказ казать, что они не контекстно-сво одн б ные.
Первый пример показывает, что хо ов могут иметь по две соответствующие друг другу ц елочки контекстно-свободных языков могут и. группы символов, , но три такие группы уже невозможны. со нПример 7.19. Пусть Ь = 10 ~ ~и, т.. ° с о — "1"2" ~ > 1), т.е. 2, состоит из цепочек вида 0 1 2 с од- п име, 012, 00! 122 и т.д. Предполонаковыми количествами каждого из символов, например, ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 290 жви, что Е контекстно-свободный. Тогда сушествует целое и из леммы о накачке. Вы- 2 берем е = О" 1 "2".
а) и н у б) в) к п х Рис. 7.7. Накачивание цепочек т их Ораз и 7 раза Предположим, что "противник" разбивает е как х = изчеху, где )тзгх~ < и и и и х не равны е елвовременно. Тогда нам известно, что зчех не может включать одновременно нули и двойш, поскольку последний нуль и первая двойка разделены и+ 1 позициями. Докажем, что Е содержит некоторую цепочку, которая не может быть в Д получив тем самым противоречле к предположению, что Т, контекстно-свободный. Возможны следующие случаи. 1. твх не имеет двоек, т.е, тх состоит только из нулей и единиц и содержит хотя бы один из этих символов. Тогда цепочка иьчу, которая по лемме о накачке должна быть в Д имеет и двоек, но меньше, чем и нулей или единиц.
Следовательно, она не принадлежит Д и в этом случае Т. не контекстно-свободен, ' Напомним, что это п есть константа, обеслеченнал леммой о накачке н не имеющая ничего общего с локальной переменной и, использованной в определении языка 1.. 1.2. ЛЕММА О НАКАЧКЕ ДЛЯ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 291 2, тих не имеет нулей. Аналогично, ииу имеет л нулей, но меньше двоек или единиц, поэтому не принадлежит Е. В любом случае приходим к выводу, что Е содержит цепочку, которая не может ему принадлежать.
Это про~иворечие позволяет заключить, что наше предположение ложно, т.е. Е не является КС-языком. П Еше одно свойство КС-языков состоит в том, что в их цепочках не может быть двух соответствующих друг другу перемежающихся пар равных количеств символов. Эта идея уточняется следуюшим примером. Пример 7.20. Пусть Е = (О'1'2'3' ) ! > 1 и ! > 1) . Если он контекстно-свободен, то пусть л — константа для Е, и выберем - = 0" 1 "2"3". Можно записать х = игиху, соблюдая обычные ограничения )тгех~ < и и гх и е. Тогда тих или состоит из символов одного вида, или захватывает символы двух различных соседних видов. Если иих состоит из символов одного вида, то ииу имеет по л символов трех различных видов и меньше, чем л символов четвертого вида.
Таким образом, ииу не может быль в Е. Если игх захватывает символы двух различных соседних видов, скажем, единицы и двойки, то в изгу их не хватает. Если не хватает единиц, то, поскольку там есть и троек, эта цепочка не может быть в Е. Если же не хватает двоек, то изгу также не может быть в Е, поскольку содержит и нулей.
Получаем противоречие к предположению о том, что Š— КС-язык, и приходим к выводу, что он таковым не является. П В заключительном примере покажем, что в цепочках КС-языков не может быть двух одинаковых цепочек произвольной длины, если они выбираются в алфавите, состоящем более чем из одного символа. Следствием этого замечания, между прочим, является то, что КС-грамматики не являются подходящим механизмом для описания определенных "семантических" ограничений в языках программирования, например, что идентификатор должен быть объявлен до его использования.
На практике для запоминания объявленных идентификаторов используется другой механизм, "таблица символов", и никто не пытается строить синтаксический анализатор, который проверял бы соблюдение принципа "определение до использования". Пример 7.21.
Пусть Е = (иж) мц (О, 1) ), т.е. Е состоит из повторяющихся цепочек, например, е, 0101, 00100010 или 110110. Если он контекстно-свободный, то пусть и — константа из леммы о накачке для Е. Рассмотрим цепочку г = 0"1"0"1". Очевидно, - ц Е. Следуя шаблону предыдуших примеров, можно записать - = и1 иху, причем )тих) < и и гх к е. Покажем, что ииу не принадлежит Е, тем самым доказав от про~ивного, что Е не может быть КС-языком. Заметим сразу, что, поскольку )гзех) < л, то )ииу) > Зп. Таким образом, если иму является повторением цепочки, скажем, а, то г имеет длину не менее Зи/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
