Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 66
Текст из файла (страница 66)
Возможны не- сколько вариантов в зависимости от расположения чих в пределах х. 292 ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 1. Предположим, игх находится в пределах первых и нулей. Для определенности пусть тх состоит из к нулей, где к > О. Тогда ину начинается с 0" "1". Поскольку !ину! = 4н — к и по предположению иву = и, то ф = 2п — хг2.
Такилг образом, г не заканчивается впервом блоке из единиц, т.е. заканчивается символом О. Но ииу заканчивается единицей, поэтому не может равняться гл Предположим, тих захватывает первый блок нулей и первый блок единиц. Возможно, тх состоит только из нулей, если х = а Тогда иму не может быть вида и по той же причине, что и в случае ! . Если же их содержит хотя бы одну единицу, то Е длина которой не менее 3и/2, должна заканчиваться на 1", поскольку ииу заканчивается на 1". Однако из и единиц состоит только последний блок в ииу, поэтому г не может повторяться в иву. 3.
Если итх содержится в первом блоке единиц, то игйу не может быть в Е по тем же причинам, что и во второй части случая 2. Предположим, тггх захватывает первый блок единиц и второй блок нулей. Если тх не имеет нулей, то все получается так же, как если бы тих содержалась в первом блоке единиц. Если тх содержит хотя бы один нуль, то иму начинается блоком из и нулей, как и г, если ииу = и. Однако в ижу второго блока нз н нулей для г нет, поэтому ижу не может быть в Е. В остальных случаях, когда игх находится во второй части ", аргументы симметричны по отношению к случаям, когда тих содержится в первой части:. Итак, в любом случае ину не принадлежит Е, и мы приходим к выводу, что Е не контек- стаа-свободный.
7.2.4. Упражнения к разделу 7.2 !.2.!. Используйте лемму о накачке для КС-языков, чтобы показать, что каждый из следующих языков не контекстно-свободный. а) (ь) (а'Ыс (1<)'< Ц; б) (а"Ь"с' ) г' Б н); в) (О'(р — простое). Указание. Используйте те же иден, что и в примере 4.3, где доказывалась нерегулярность этого языка; г) (е!) (О'11! у = ! ); д) (!) (а"Ь'С / и < ! < 2н); е) (!) (нзг и / в — цепочка из нулей и единиц), т.е. множество цепочек, состоящих из цепочки гг, за которой записаны ее обращение и она же еще раз, например 001100001.
7.2. ЛЕММА О НАКАЧКЕ ДЛЯ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 293 7.2.2. (!) Когда мы пытаемся применить лемму о накачке к КС-языку, "выигрывает противник", и нам не удается завершить доказательство. Покажите, что является ошибочным, когда в качестве Ь выбирается один из следующих языков: а) (00, 11); б) (') (О"1"! и > 1); в) (» ) множество палиндромов в алфавите (О, 1). 7.2З. (!) Существует более сильная версия леммы о накачке для КС-языков, известная как лемма Огдена. Она отличается от доказанной леммы о накачке тем, что по- зволяет нам сосредоточиться на любых и "выделенных" позициях цепочки г и гарантирует, что накачиваемые цепочки содержат от 1 до и выделенных позиций. Преимущество этого свойства в том, что язык может иметь цепочки, состоящие из двух частей, одна из которых может быть накачана без создания цепочек, не принадлежащих языку, тогда как вторая при накачке обязательно порождает цепочки вне языка. Если мы не можем утверждать, что накачка имеет место во второй части, то мы не можем завершить доказательство того, что язык не контекстно-свободный.
Формальное утверждение леммы Огдена состоит в следующем. Для любого КС-языка Ь существует такая константа и, что если г— произвольная цепочка из Ь длиной не менее п, в которой выделено не менее и различных позиций, то г можно записать в виде иг«кху, причем выполняются следующие условия. 1.
гих имеет не более и выделенных позиций. 2, гх имеет хотя бы одну выделенную позицию. 3. иг'и«хун Ь для всех 1> О. Докажите лемму Огдена. Указание. Доказательство на самом деле весьма похоже на доказательство леммы о накачке (теорема 7.18), если мы представим себе, что в том доказательстве невыделенные позиции цепочки г отсутствуют, когда выбирается длинный путь в дереве разбора для г. 7,2.4. («) Используйте лемму Огдена (упражнение 7.2.3) для упрощения доказательства того, что Ь = (ни ! ие (О, 1) ) — не КС-язык (см.
пример 7.21). Указание. В выбранной цепочке г сделайте выделенной только одну группу из н последова- тельных символов. 7.2.5. Используйте лемму Огдена (упражнение 7.2.3) для доказательства того, что следующие языки не являются контекстно-свободными: а) (!) (О'1!О" !у= шах(Ь 1«)); б) (!!) (а Ьс' !1~ и). Указание.
Рассмотрите цепочку г= а Ь с", где п — константа из леммы Огдена. ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 294 7.3. Свойства замкнутости контекстно-свободных языков Рассмотрим некоторые операции над контекстно-свободными языками, которые гарантированно порождают КС-языки. Многие из этих свойств замкнутости соответствуют теоремам для регулярных языков из раздела 4.2. Однако есть и отличия. Вначале введем операцию подстановки, по которой каждый символ в цепочках из одного языка заменяется целым языком.
Эта операция обобщает гомоморфизм, рассмотренный в разделе 4.2.3, и является полезной в доказательстве свойств замкнутости КС- языков, относительно некоторых других операций, например, регулярных (объединение, конкатенация и замыкание). Покажем, что КС-языки замкнуты относительно гомоморфазма и обратного гомоморфизма. В отличие от регулярных языков, КС-языки не замквутм относительно пересечения и разности. Однако пересечение или разность КС-языка я ре~улярного языка всегда является КС-языком. 7.3.1.
Подстановки Пусть Б — алфавит. Предположим, для каждого символа а из Б выбран язык Л,. Выбранные языки могут быть в любых ачфавитах, не обязательно Б и не обязательно одиааковых. Выбор языков определяет функцию «(подстановка, зцЬ«11гцг(оп) на Х, и Ь обозаачается как «(а) для каждого символа а. Если ю = ал«,...а„— цепочка из Х, то «(и) представляет собой язык всех цепочек хохл ..х„, у которых для 1 = 1, 2, ..., и цепочка х, принадлежит языку «(а,). Иными словами, «(в) является конкатенацией языков «(а,)«(а«)..ж(а„).
Определение «можно распростраяигь на языки: «(Ь) — это объединение «(и) по всем цепочкам ч«из Ь. Пример 7.22. Пусть «(О) = ( а"Ь" ~ и > 1) и «(1) = ( аа, ЬЬ), т.е, « — подстановка на алфавите Х= (О, 1), Язык «(О) представляет собой множество цепочек с одним или несколькими символами а, за которыми следует такое же количество Ь, а «(1) — конечный я«ых, состоящий из двух цепочек аа и ЬЬ. Пусть в = 01. Тогда «(ч) есть конкатенация языков «(0)«(1).
Точнее, «(и) состоит из всех цепочек вида а'Ь"аа и а Ь" ~, где л > 1. Теперь предположим, что Ь =ЦО), т.е. множество всех цепочек из нулей. Тогда й() = («(О)) . Этот язык представляет собой множество всех цепочек вида ви некоторого 1 > 0 и произвольной последовательности положительных целых лл нъ аь Ов включает, например, цепочки к ааЬЬаааЬЬЬ и аЬааЬЬаЬаЬ. С) Теорема 7.23.
Если 7. — КС-язык в алфавите Б, а « — подстановка на Х, при которой йа) является КС-языком для каждого а из Б, то «(Л) также является КС-языком. Доказательство. Основная идея состоит в том, что мы можем взять КС-грамматику яяя Ь и заменить каждый термннач а стартовым символом грамматики для языка «(а). В 7,3. СВОЙСТВА ЗАМКНУТОСТИ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 295 результате получим единственную грамматику, порождающую «(Б).
Однако тут нужно быть аккуратным. Более формально, пусть грамматика О = (К, Х, Р, о) задает язык Т., а грамматика б„= ((гт Т„Р 8 ) — язык, подставляемый вместо каждого а из Х. Поскольку для переменных можно выбирать любые имена, обеспечим, чтобы множества имен переменных 1' и ~; (для всех а) не пересекались. Цель такого выбора имен — гарантировать, что при сборе продукций разных грамматик в одно множество невозможно случайно смешать продукции двух грамматик, и, таким образом, получить порождения, невозможные в данных грамматиках. Построим новую грамматику С'= (Р; Т; Р; 8) для «(7) слелукнцим образом.
° (г'представляет собой обьединение (г и всех К, по а из Х. ° Т'является обьединением Т„по а из Б. ° Р'состоит из следующих продукций. 1. Все продукции каждого из Р, для а из Х. 2, Все продукции Р, но с изменением везде в их телах каждого терминала а на 8,. Таким образом, все деревья разбора в грамматике с 'начинаются как деревья разбора в О, но вместо того, чтобы порождать крону в Х, они содержат границу, на которой все узлы отмечены переменными 5, вместо а из Б. Каждый такой узел является корнем дерева в 0„, крона которого представляет собой терминальную цепочку из «(а) (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
