dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 65
Текст из файла (страница 65)
Каждая достаточно длинная цепочка в L должна иметьдлинный путь в своем дереве разбораЕсли Ai = Aj = A, то по исходному дереву можно построить новое дерево разбора, какпоказано на рис. 7.7, а. Сначала можно заменить поддерево с корнем Ai, имеющее кронуvwx, поддеревом с корнем Aj, у которого крона w. Это допустимо, поскольку корни обоихподдеревьев отмечены одной и той же переменной A. Полученное дерево представленона рис. 7.7, б. Оно имеет крону и соответствует случаю i = 0 в шаблоне цепочек uviwxiy.Еще одна возможность представлена на рис. 7.7, в.
Там поддерево с корнем Aj заменено поддеревом с корнем Ai. Допустимость этой замены также обусловлена тем, чтоотметки корней совпадают. Кроной этого дерева является uv2wx2y. Если бы мы затем заменили поддерево с кроной w (см. рис. 7.7, в) большим поддеревом с кроной vwx, то получили бы дерево с кроной uv3wx3y и так далее для любого показателя i. Итак, в G существуют деревья разбора для всех цепочек вида uviwxiy, и лемма о накачке почти доказана.Осталось условие 1, гласящее, что |vwx| ≤ n. Мы выбирали Ai как можно ближе к кроне дерева, поэтому k – i ≤ m. Таким образом, самый длинный путь в поддереве с корнем7.2. ËÅÌÌÀ Î ÍÀÊÀ×ÊÅ ÄËß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр.
289289Ai имеет длину не более m + 1. По теореме 7.17 поддерево с корнем Ai имеет крону, длина которой не больше, чем 2m = n. i=jjРис. 7.6. Разделение цепочки z для накачивания7.2.3. Ïðèëîæåíèÿ ëåììû î íàêà÷êå ê ÊÑ-ÿçûêàìОтметим, что лемма о накачке для КС-языков, как и для регулярных языков, используется в виде “игры с противником” следующим образом.1.Мы выбираем язык L, желая доказать, что он не контекстно-свободный.2.Наш “противник” выбирает заранее неизвестное нам n, поэтому мы должны рассчитывать на любое возможное значение.3.Мы выбираем z и при этом можем использовать n как параметр.4.Противник разбивает z на uvwxy, соблюдая ограничения |vwx| ≤ n и vx ≠ ε.5.Мы “выигрываем”, если можем, выбирая i и показывая, что uviwxiy не принадлежит языку L.Рассмотрим несколько примеров языков, о которых с помощью леммы о накачкеможно доказать, что они не контекстно-свободные.
Первый пример показывает, что хотяцепочки контекстно-свободных языков могут иметь по две соответствующие друг другугруппы символов, но три такие группы уже невозможны.Пример 7.19. Пусть L = {0n1n2n | n ≥ 1}, т.е. L состоит из цепочек вида 0+1+2+ с одинаковыми количествами каждого из символов, например, 012, 001122 и т.д. Предполо-290Стр. 290ÃËÀÂÀ 7.
ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂжим, что L контекстно-свободный. Тогда существует целое n из леммы о накачке.2 Выберем z = 0n1n2n.а)б)в)Рис. 7.7. Накачивание цепочек v и x 0 раз и 2 разаПредположим, что “противник” разбивает z как z = uvwxy, где |vwx| ≤ n и v и x не равны εодновременно. Тогда нам известно, что vwx не может включать одновременно нули и двойки, поскольку последний нуль и первая двойка разделены n + 1 позициями. Докажем, что Lсодержит некоторую цепочку, которая не может быть в L, получив тем самым противоречие к предположению, что L контекстно-свободный.
Возможны следующие случаи.vwx не имеет двоек, т.е. vx состоит только из нулей и единиц и содержит хотя быодин из этих символов. Тогда цепочка uwy, которая по лемме о накачке должна быть1.2Напомним, что это n есть константа, обеспеченная леммой о накачке и не имеющая ничегообщего с локальной переменной n, использованной в определении языка L.7.2. ËÅÌÌÀ Î ÍÀÊÀ×ÊÅ ÄËß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр.
291291в L, имеет n двоек, но меньше, чем n нулей или единиц. Следовательно, она не принадлежит L, и в этом случае L не контекстно-свободен.2.vwx не имеет нулей. Аналогично, uwy имеет n нулей, но меньше двоек или единиц,поэтому не принадлежит L.В любом случае приходим к выводу, что L содержит цепочку, которая не может емупринадлежать.
Это противоречие позволяет заключить, что наше предположение ложно,т.е. L не является КС-языком. Еще одно свойство КС-языков состоит в том, что в их цепочках не может быть двухсоответствующих друг другу перемежающихся пар равных количеств символов. Этаидея уточняется следующим примером.Пример 7.20. Пусть L = {0i1j2i3j | i ≥ 1 и j ≥ 1}. Если он контекстно-свободен, то пустьn — константа для L, и выберем z = 0n1n2n3n. Можно записать z = uvwxy, соблюдая обычные ограничения |vwx| ≤ n и vx ≠ ε. Тогда vwx или состоит из символов одного вида, илизахватывает символы двух различных соседних видов.Если vwx состоит из символов одного вида, то uwy имеет по n символов трех различных видов и меньше, чем n символов четвертого вида.
Таким образом, uwy не можетбыть в L. Если vwx захватывает символы двух различных соседних видов, скажем, единицы и двойки, то в uwy их не хватает. Если не хватает единиц, то, поскольку там есть nтроек, эта цепочка не может быть в L. Если же не хватает двоек, то uwy также не можетбыть в L, поскольку содержит n нулей. Получаем противоречие к предположению о том,что L — КС-язык, и приходим к выводу, что он таковым не является.
В заключительном примере покажем, что в цепочках КС-языков не может быть двуходинаковых цепочек произвольной длины, если они выбираются в алфавите, состоящемболее чем из одного символа. Следствием этого замечания, между прочим, является то,что КС-грамматики не являются подходящим механизмом для описания определенных“семантических” ограничений в языках программирования, например, что идентификатор должен быть объявлен до его использования. На практике для запоминания объявленных идентификаторов используется другой механизм, “таблица символов”, и никтоне пытается строить синтаксический анализатор, который проверял бы соблюдениепринципа “определение до использования”.Пример 7.21. Пусть L = {ww | w∈{0, 1}*}, т.е.
L состоит из повторяющихся цепочек, например, ε , 0101, 00100010 или 110110. Если он контекстно-свободный, топусть n — константа из леммы о накачке для L. Рассмотрим цепочку z = 0 n1 n0 n1 n.Очевидно, z ∈ L.Следуя шаблону предыдущих примеров, можно записать z = uvwxy, причем |vwx| ≤ n иvx ≠ ε. Покажем, что uwy не принадлежит L, тем самым доказав от противного, что L неможет быть КС-языком.292Стр. 292ÃËÀÂÀ 7.
ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂЗаметим сразу, что, поскольку |vwx| ≤ n, то |uwy| ≥ 3n. Таким образом, если uwy является повторением цепочки, скажем, tt, то t имеет длину не менее 3n/2. Возможны несколько вариантов в зависимости от расположения vwx в пределах z.1.Предположим, vwx находится в пределах первых n нулей. Для определенности пусть vxсостоит из k нулей, где k > 0. Тогда uwy начинается с 0n–k1n. Поскольку |uwy| = 4n – kи по предположению uwy = tt, то |t| = 2n – k/2. Таким образом, t не заканчиваетсяв первом блоке из единиц, т.е. заканчивается символом 0. Но uwy заканчиваетсяединицей, поэтому не может равняться tt.2.Предположим, vwx захватывает первый блок нулей и первый блок единиц.
Возможно, vx состоит только из нулей, если x = ε. Тогда uwy не может быть вида tt потой же причине, что и в случае 1. Если же vx содержит хотя бы одну единицу, то t,длина которой не менее 3n/2, должна заканчиваться на 1n, поскольку uwy заканчивается на 1n. Однако из n единиц состоит только последний блок в uwy, поэтому tне может повторяться в uwy.3.Если vwx содержится в первом блоке единиц, то uwy не может быть в L по тем жепричинам, что и во второй части случая 2.4.Предположим, vwx захватывает первый блок единиц и второй блок нулей.
Если vxне имеет нулей, то все получается так же, как если бы vwx содержалась в первомблоке единиц. Если vx содержит хотя бы один нуль, то uwy начинается блоком из nнулей, как и t, если uwy = tt. Однако в uwy второго блока из n нулей для t нет, поэтому uwy не может быть в L.5.В остальных случаях, когда vwx находится во второй части z, аргументы симметричны по отношению к случаям, когда vwx содержится в первой части z.Итак, в любом случае uwy не принадлежит L, и мы приходим к выводу, что L не контекстно-свободный.7.2.4. Óïðàæíåíèÿ ê ðàçäåëó 7.27.2.1.Используйте лемму о накачке для КС-языков, чтобы показать, что каждый изследующих языков не контекстно-свободный.а) (∗) {aibjck | i < j < k};б) {anbnci | i ≤ n};в) {0p | p — простое}. Указание. Используйте те же идеи, что и в примере 4.3,где доказывалась нерегулярность этого языка;г) (∗!) {0i1j | j = i2};д) (!) {anbnci | n ≤ i ≤ 2n};7.2.
ËÅÌÌÀ Î ÍÀÊÀ×ÊÅ ÄËß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 293293е) (!) {wwRw | w — цепочка из нулей и единиц}, т.е. множество цепочек, состоящих из цепочки w, за которой записаны ее обращение и она же еще раз,например 001100001.7.2.2.(!) Когда мы пытаемся применить лемму о накачке к КС-языку, “выигрываетпротивник”, и нам не удается завершить доказательство. Покажите, что являетсяошибочным, когда в качестве L выбирается один из следующих языков:а) {00, 11};б) (∗) {0n1n | n ≥ 1};в) (∗) множество палиндромов в алфавите {0, 1}.7.2.3.(!) Существует более сильная версия леммы о накачке для КС-языков, известнаякак лемма Огдена. Она отличается от доказанной леммы о накачке тем, что позволяет нам сосредоточиться на любых n “выделенных” позициях цепочки z и гарантирует, что накачиваемые цепочки содержат от 1 до n выделенных позиций.
Преимущество этого свойства в том, что язык может иметь цепочки, состоящие издвух частей, одна из которых может быть накачана без создания цепочек, не принадлежащих языку, тогда как вторая при накачке обязательно порождает цепочкивне языка.
Если мы не можем утверждать, что накачка имеет место во второй части, то мы не можем завершить доказательство того, что язык не контекстносвободный. Формальное утверждение леммы Огдена состоит в следующем. Длялюбого КС-языка L существует такая константа n, что если z — произвольная цепочка из L длиной не менее n, в которой выделено не менее n различных позиций,то z можно записать в виде uvwxy, причем выполняются следующие условия.1.vwx имеет не более n выделенных позиций.2.vx имеет хотя бы одну выделенную позицию.3.uviwxiy ∈ L для всех i ≥ 0.Докажите лемму Огдена. Указание.
Доказательство на самом деле весьма похоже на доказательство леммы о накачке (теорема 7.18), если мы представим себе,что в том доказательстве невыделенные позиции цепочки z отсутствуют, когдавыбирается длинный путь в дереве разбора для z.7.2.4.(∗) Используйте лемму Огдена (упражнение 7.2.3) для упрощения доказательства того, что L = {ww | w∈{0, 1}*} — не КС-язык (см. пример 7.21). Указание. Ввыбранной цепочке z сделайте выделенной только одну группу из n последовательных символов.7.2.5.Используйте лемму Огдена (упражнение 7.2.3) для доказательства того, что следующие языки не являются контекстно-свободными:а) (!) {0i1j0k | j = max(i, k)};294Стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
