dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 66
Текст из файла (страница 66)
294ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂб) (!!) {anbnci | i ≠ n}. Указание. Рассмотрите цепочку z = anbncn!, где n — константа из леммы Огдена.7.3. Ñâîéñòâà çàìêíóòîñòè êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâРассмотрим некоторые операции над контекстно-свободными языками, которые гарантированно порождают КС-языки. Многие из этих свойств замкнутости соответствуюттеоремам для регулярных языков из раздела 4.2. Однако есть и отличия.Вначале введем операцию подстановки, по которой каждый символ в цепочках из одного языка заменяется целым языком. Эта операция обобщает гомоморфизм, рассмотренный в разделе 4.2.3, и является полезной в доказательстве свойств замкнутости КСязыков, относительно некоторых других операций, например, регулярных (объединение,конкатенация и замыкание).
Покажем, что КС-языки замкнуты относительно гомоморфизма и обратного гомоморфизма. В отличие от регулярных языков, КС-языки не замкнуты относительно пересечения и разности. Однако пересечение или разность КС-языкаи регулярного языка всегда является КС-языком.7.3.1. ÏîäñòàíîâêèПусть Σ — алфавит. Предположим, для каждого символа a из Σ выбран язык La. Выбранные языки могут быть в любых алфавитах, не обязательно Σ и не обязательно одинаковых. Выбор языков определяет функцию s (подстановка, substitution) на Σ, и La обозначается как s(a) для каждого символа a.Если w = a1a2…an — цепочка из Σ*, то s(w) представляет собой язык всех цепочекx1x2…xn, у которых для i = 1, 2, …, n цепочка xi принадлежит языку s(ai).
Иными словами,s(w) является конкатенацией языков s(a1)s(a2)…s(an). Определение s можно распространить на языки: s(L) — это объединение s(w) по всем цепочкам w из L.Пример 7.22. Пусть s(0) = {anbn | n ≥ 1} и s(1) = {aa, bb}, т.е. s — подстановка на алфавите Σ = {0, 1}. Язык s(0) представляет собой множество цепочек с одним или несколькими символами a, за которыми следует такое же количество b, а s(1) — конечныйязык, состоящий из двух цепочек aa и bb.Пусть w = 01. Тогда s(w) есть конкатенация языков s(0)s(1). Точнее, s(w) состоит извсех цепочек вида anbnaa и anbn+2, где n ≥ 1.Теперь предположим, что L = L(0*), т.е.
множество всех цепочек из нулей. Тогдаs(L) = (s(0))*. Этот язык представляет собой множество всех цепочек видаa n1 b n1 a n2 b n2 K a nk b nkдля некоторого k ≥ 0 и произвольной последовательности положительных целых n1, n2, …,nk. Он включает, например, цепочки ε, aabbaaabbb и abaabbabab. Теорема 7.23. Если L — КС-язык в алфавите Σ, а s — подстановка на Σ, при которойs(a) является КС-языком для каждого a из Σ, то s(L) также является КС-языком.7.3.
ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 295295Доказательство. Основная идея состоит в том, что мы можем взять КС-грамматикудля L и заменить каждый терминал a стартовым символом грамматики для языка s(a). Врезультате получим единственную грамматику, порождающую s(L). Однако тут нужнобыть аккуратным.Более формально, пусть грамматика G = (V, Σ, P, S) задает язык L, а грамматикаGa = (Va, Ta, Pa, Sa) — язык, подставляемый вместо каждого a из Σ. Поскольку для переменных можно выбирать любые имена, обеспечим, чтобы множества имен переменныхV и Va (для всех a) не пересекались. Цель такого выбора имен — гарантировать, что присборе продукций разных грамматик в одно множество невозможно случайно смешатьпродукции двух грамматик, и, таким образом, получить порождения, невозможные вданных грамматиках.Построим новую грамматику G′ = (V′, T′, P′, S) для s(L) следующим образом.• V′ представляет собой объединение V и всех Va по a из Σ.• T′ является объединением Ta по a из Σ.• P′ состоит из следующих продукций.1.Все продукции каждого из Pa для a из Σ.2.Все продукции P, но с изменением везде в их телах каждого терминала a на Sa.Таким образом, все деревья разбора в грамматике G′ начинаются как деревья разбора вG, но вместо того, чтобы порождать крону в Σ*, они содержат границу, на которой всеузлы отмечены переменными Sa вместо a из Σ.
Каждый такой узел является корнем дерева в Ga, крона которого представляет собой терминальную цепочку из s(a) (рис. 7.8).SSa1x1Sa2Sanx1xnРис. 7.8. Дерево разбора в G′ начинается деревом разбора в G и заканчиваетсямногими деревьями, соответствующими грамматикам GaДокажем, что описанная конструкция правильна в том смысле, что G′ порождаетязык s(L). Формально будет доказано следующее утверждение.• Цепочка w принадлежит L(G′) тогда и только тогда, когда w принадлежит s(L).296Стр. 296ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂ(Достаточность) Пусть w принадлежит s(L). Тогда существует цепочка x = a1a2…anв L и такие цепочки xi в s(ai) при i = 1, 2, …, n, для которых w = x1x2…xn. Тогда часть G′,образованная продукциями из G с подстановками Sa вместо каждого a, порождает цепочку, которая выглядит, как x, но с Sa вместо каждого a, т.е.
цепочку Sa1Sa2…San. Эта частьпорождения w представлена верхним треугольником на рис. 7.8.Продукции каждой Ga являются также продукциями G′, поэтому порождение xi из Saiесть также порождение в G′. Деревья разбора для этих порождений представлены нарис. 7.8 нижними треугольниками. Поскольку крона этого дерева разбора в G′ естьx1x2…xn = w, приходим к выводу, что w принадлежит L(G′).(Необходимость) Предположим, что w принадлежит L(G′).
Утверждаем, что дереворазбора для w должно выглядеть, как дерево на рис. 7.8. Причина в том, что переменные каждой из грамматик G и Ga для a из Σ попарно различны. Таким образом, верхушка дерева, начинающаяся переменной S, должна использовать только продукции Gдо тех пор, пока не будет порожден некоторый символ Sa, а под этим символом могутиспользоваться только продукции грамматики Ga. В результате, если w имеет дереворазбора T, можно выделить цепочку a1a2…an в L(G) и цепочки xi в языках s(ai), для которых верно следующее.1.w = x1x2…xn.2.Цепочка Sa1Sa2…San является кроной дерева, образованного из T удалением некоторых поддеревьев (см.
рис. 7.8).Но цепочка x1x2…xn принадлежит s(L), поскольку образована подстановкой цепочек xiвместо каждого из ai. Таким образом, делаем вывод, что w принадлежит s(L). 7.3.2. Ïðèëîæåíèÿ òåîðåìû î ïîäñòàíîâêåС использованием теоремы 7.23 можно обосновать несколько свойств замкнутости,хорошо знакомых нам по регулярным языкам. Перечислим их в следующей теореме.Теорема 7.24. Контекстно-свободные языки замкнуты относительно следующихопераций.1.Объединение.2.Конкатенация.3.Замыкание (*) и транзитивное замыкание (+).4.Гомоморфизм.Доказательство. Каждое утверждение требует лишь определения соответствующейподстановки. Каждое из следующих доказательств использует подстановку контекстносвободных языков в другие, в результате чего по теореме 7.23 порождаются КС-языки.1.Объединение.
Пусть L1 и L2 — КС-языки. Тогда L1 U L2 является языком s(L), гдеL — язык {1, 2}, а s — подстановка, определяемая как s(1) = L1 и s(2) = L2.7.3. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 2972972.Конкатенация. Пусть L1 и L2 — КС-языки. Тогда L1L2 представляет собой язык s(L),где L — язык {12}, а s — такая же подстановка, как и в п. 1.3.Замыкание и транзитивное замыкание. Если L1 — КС-язык, L — язык {1}*, а s —подстановка s(1) = L1, то L1* = s(L).
Аналогично, если в качестве L взять язык {1}+,то L1+ = s(L).4.Пусть L — КС-язык над алфавитом Σ, и h — гомоморфизм на Σ. Пусть s — подстановка, заменяющая каждый символ a из Σ языком, состоящим из единственной цепочки h(a), т.е. s(a) = {h(a)} для всех a из Σ. Тогда h(L) = s(L). 7.3.3. ÎáðàùåíèåКС-языки замкнуты также относительно обращения. Для доказательства этого фактаиспользовать теорему о подстановках нельзя, но существует простая конструкция на основе грамматик.Теорема 7.25. Если L — КС-язык, то и LR — КС-язык.Доказательство.
Пусть L — L(G) для некоторой КС-грамматики G = (V, T, P, S). Построим GR = (V, T, PR, S), где продукции PR представляют собой “обращения” продукцийиз P. Таким образом, если A → α — продукция G, то A → αR — продукция GR. С помощью индукции по длине порождений в G и GR нетрудно показать, что L(GR) = LR.
По сути, все выводимые в GR цепочки являются обращениями цепочек, выводимых в G, и наоборот. Формальное доказательство оставляется в качестве упражнения. 7.3.4. Ïåðåñå÷åíèå ñ ðåãóëÿðíûì ÿçûêîìКС-языки не замкнуты по пересечению. Это доказывает следующий простой пример.Пример 7.26. В примере 7.19 было выяснено, что языкL = {0n1n2n | n ≥ 1}не является контекстно-свободным. Однако следующие два — контекстно-свободные.L = {0n1n2i | n ≥ 1, i ≥ 1}L = {0i1n2n | n ≥ 1, i ≥ 1}Первый из них порождается следующей грамматикой.S → ABA → 0A1 | 01B → 2B | 2В этой грамматике A порождает все цепочки вида 0n1n, а B — все последовательностидвоек.
Аналогична и грамматика для второго языка.S → ABA → 0A | 0B → 1B2 | 12298Стр. 298ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂЗдесь A порождает все последовательности нулей, а B — цепочки вида 1n2n.Однако L = L1 I L2. Чтобы в этом убедиться, заметим, что L1 требует равных количеств нулей и единиц в цепочках, тогда как L2 — равных количеств единиц и двоек. Поэтому цепочка из пересечения этих языков должна иметь поровну каждого из символови, следовательно, принадлежать L.Если бы КС-языки были замкнуты по пересечению, то мы могли бы доказать ложноеутверждение о том, что L — контекстно-свободный язык. Полученное противоречие позволяет заключить, что КС-языки не замкнуты по пересечению. Вместе с тем, есть более слабое утверждение о пересечении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
