Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 45
Текст из файла (страница 45)
221 ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Так как и, имеет 12"+2 выделенных потомков, то путь и;, ...,пр содержит по крайней мере 2т+3 ветвящихся вершин. Кроме того, пр — лист, и потомУ он ее ЯвлЯетсЯ ветвЯЩейсЯ веРшиной. Следовательно, р > 2т+3. Пусть Ь„Ь„..., Ь, „,— это последние 2т+3 вершины, принадлежащие пути и„, ..., пр.
Назовем Ь, левой ветвящейся верн>иной, если прямой потомок вершины Ьг, не принадлежащий этомУ пУти, имеет выДеленного потомка слева от пр. В пРотивном случае будем называть Ь, правой ветвящейся вершиной. Предположим, что по крайней мере т+2 вершины из Ь„..., Ь,„„левыс ветвящиеся. Случай, когда по крайней мере т+ 2 вершины правые ветвящиеся, исследуется аналогично. Ряс, 237. Дерева вывода Т, Пусть 1,, 1„..., 1„+,— последние т+2 левые ветвящиеся вершины последовательности Ь„., „Ь, ~2.
Так как 4ЬХ =пг, то среди 1„..., 1„„, можно нанти две вершины, скажем 1> и 1, с одной и той же меткой, скажем А, и 1< д. Эта ситуация изображена на рис. 2. !7. Двойной линией показан путьпм ..., и, звездочки указывают выделенные листья (кроме этих могут быть н другие). Если удалить всех потомков вершины 1, то получится дерево вывода с кроной иАу, где и состоит из листьев, расположенных слева От 1, а у — из листьев, расположенных справа. Таким образом, 1~" иАу. Если мы рассмотрим поддерево с корнем 1>, из которого удалены потомки вершины 1, то увидим, что А =>" оЛх, где о и х — части кроны этого йоддерева, состоящие из листьев, расположенных соответственно слева и справа от1 . Наконец, пусть и> — крона поддерева с корнем 1.
Тогда А =р го и, значит, з = иоюху. 222 2.а. Овойствх НОнтекстнО.своеОдных языкОе Объединяя эти выводы, получаем Я=Ь+ иАу=>е игоу н для всех г) 1 5 =>~ иАу =э+ иоАху =э+ ио Лх у =>+... ~+ ио Ах у =э+ носи>хгу Таким образом, условие (4) выполнено. Кроме того, цепочка и имеет хотя бы одну выделенную позицию, которую занимает потомок некоторого прямого потомка вершины 1„.
Аналогично цепочка о имеет хотя бы одну выделеш|ую позицию, которую занимает потомок вершины 1>. Следовательно, условие (2) тоже выполнено. Условие (!) выполняется потому, что цепочка и> имеет выделенную позицию, а именно ту, которую занимает и . Чтобы проверить выполнение условия (3), состоящего в том, что цепочка оп>х имеет не более й выделенных позиций, заметим, что цепочка Ь„будучи (2т+ 3)-й ветвящейся вершиной от конца пути и„..., и, имеет не более й выделенных позиций. Так как 1 — потомок вершины Ь„отсюда иееосредственно следует нужный результат, Надо было бы рассмотреть еще противоположный случай, когда по крайней мере т+2 вершин из Ь„..., Ь... правые ветвящиеся.
Однако здесь можно рассуждать по симметрии, и в итоге мы обнаружим, что условие (2) выполняется, так как каждая из цепочек х и у имеет выделенные позиции. Докажем важное следствие леммы Огдеиа, которое иногда называют леммой о разрастании для КС-языков.
Следствие. Пусть 1. — КС-язых. Тогда существует такая константа й, что если )2! ==А и 2ЕЕ, то 2 можно представить в виде з=.-иогоху, где охФе, ! огох)-=)г и ноги>хгуЕ7. для всех г" -О. Доказательство. В теореме 2,24 взять какую-нибудь КС-грамматику для языка 7. и считать все позиции во всех цепочках выделенными. Г1 Именно этим следствием из теоремы 2,24 мы будем чаще всего пользоваться при доказательстве того, что некоторые языки не контекстно-свободны. Самой теоремой 2.24 мы воспользуемся, когда в разд, 2.6.5 речь пойдет о существенной неоднозначности КС-языков.
Пример 2.38. С помощью леммы о разрастании покажем, что язык 1 — (а" !и' э Ц не является КС-языком. Если бы он был КС-языком, то нашлось бы такое число й, что если >>2 р:/г, то а" =иоиху, где цепочки о и х пе могут быть обе пустыми и (гтох!=-я. Пусть, в частности, п=)г. Так как и')й, то по предположению иоьихгу Е!.. Но так как ! стех )-" й, то ! е ! ох ( .я и ЬТ ( ио'гохеу ! < яь+ Й. Заметим, что следующий после я2 квадрат целого числа — число ()г+ !)2=у'+2й+ !. Так как гл. е.
элвмв нты твавии языков Й'+Й < Йь+2Й+1, то ) иочвх'у) не равно квадрату целого числа. Но по лемме о разрастании ис'вх"у Е Ь; получили противоречие. П Пример 2.39. Покажем, чта язык Ь=- (а"Ь"с" )и) 1) — не КС-язык. Если бы он был КС-языком, то мы взяли бы константу Й, которая определяется в лемме о разрастании. Пусть г=-аьЬьс".
Тогда г= — иьтсху. Так как (иох)<Й, то в цепочке твх не могут быть вхождения каждого из символов а, Ь и с. Таким образом, цепочка иву, которая по лемме о разрастании принадлежит Ь, содержит либо Й символов а, либо Й символов с. Но она не может иметь Й вхождений каждого нз символов а, Ь и с, потому что ) иву) < ЗЙ. Значит, вхождений какого-то из этих символов в иву больше, чем другого, и, следователыю, иву ~Ь. Полученное противоречие позволяет заключить, что Ь вЂ” не КС- язык.
Ц 2.6.2. Свойства замкнутости класса ИС-языков Свойства замкнутости часто помогают доказать, что некоторые языки не контекстно-свободны; кроме того, оии интересны и с теоретической точки зрения. В этом разделе мы приведем несколько основных свойств замкнутости класса КС-языков. Определение. Пусть .У вЂ” класс языков и язык Ь~Х* принадлежит .У. Допустим, что Х = — (а„..., а„) н языки 1.,„..., Ь, принадлежат,к'. Класс Я замкнут относительно псдстансвнц если для любого набора языков Ь, Ь,„..., Ь„ Ь'=(х, ... х )ай ...
а;„бЬ, х,ЕЬ,..., х„ЕЬ,, 'м' принадлежит .2'. Пример 2 40. Пусть Ь вЂ” — (О"1" )и"' 1), Ь,=(а) иЬ,=(Ь"с") т)1). Тогда результатом подстановки языков Ь, и Ь, в язык Ь будет язык Ь'=(аьЬ"'*с Ььчс'"~...Ь'"ьс» ~п '1, т,. » !) Е) Теорема 2.25., Класс КС-язынсв замкнут относительно подстановки. Д о к а з а т е л ь с т в о. Пусть Ь ы Х" — КС-язык и Х = (а;, ..., а„). Пусть Ь,ы Х„' — КС-язык для каждого аЕХ и Ь' — результат подстановки языков Ь, вместо а в цепочки языка Ь.
Пусть 6 = (51, Х, Р, 5) — КС-грамматика языка Ь и 6,=(Х„Х„Р„а')— 224 З А, Ахо, Дж. Улним, ъ ! 225 г в свояствл контекстно своьодных языка КС-грамматика языка Ь,. Предполагаем, что 14 и все Х, попар"а не пересекаются, Возьмем 6'=(51', Х', Р', 5), где (1) 51'=-0 Х,()51; ьез (2)Х=0Х,; ье Х (3) пусть Й вЂ” гомомарфизм, определенный на Я() Х н такой, что Й(А) =А для всех А ЕЬ( и Й(а) =а' для а ЕХ; положим Р'=(А — ~Й(а) ~А — ~а ЕР) 11 ! ! Р„.
ьчх Итак, Р' состоит из правил всех грамматик 6, и правил гРамматики 6, в которых все терминалы сделаны нетерминалами са штрихами. Пусть а ...ау Е Ь н х, Е Ь, для 1 <1< Й. Тогда М /4 ~ ьГ 5 =>с. а1,... а~„->с, х, а',... а~„->с,... ->в, х„... х„. Следовательно, Ь' ы Ь (6'). Допустим, что шЕЬ(6'), и рассмотрим дерево вывода Т це- почки ш.
Так как Х и 51, не пересекаются, каждый лист с мет- кой, отличной от е, имеет по крайней мере одного предка, по- меченного а', где а Е Х, Если удалить из Т каждую вершину, у которой есть предок, отличный от нее' и помеченный а' для аЕХ, та получим дерево вывода Т' с кроной а~,...а';„, где а1 ... а;„бЬ. Если х,— крона поддерева дерева Т, над которыми до- мйннрует ~'-й лист, дерева Т', то ш=х,...х„и х, ЕЬ, . Таким 'м' образом, Ь (6') = Ь' (6). Е~ Следствие, Класс КС-языков замкнут относительно (1) объеди- нения, (2) конкатенации, (3) итерации, (4) позитивной итерации и (5) гсмоморфизма.
До к а з а т е л ь с т в о. Пусть Ь, и Ьь — КС-языки, (Ц Подставим Ь, вместо а н Ь„вместо Ь в КС-язык (а, Ь1. (2) Подставим Ь, вместо а и Ьь вместо Ь в (а Ь). (3) Подставим Ь, вместо а в а', (4) Подставим Ь, вместо а в а+, (5) Для гомоморфизма Й возьмем Ь,=(Й(а)) и, подставив 5, вместо а в Ь, получим Й(Ь). П Теорема 2.25. Класс КС-яаков замкнут относительно пере- сечения с регулярными множествами. Доказательства. Нетрудно показать, что МП-автомат Р и параллельно работающий конечный автомат А можно моде- лировать подходящим МП-автоматом Р'.
Зтот составной МП-ав- томат Р' прямо моделирует Р и изменяет состояние автомата А ГЛ. Е. ЭЛГМЕ НТЫ ТЕОРИИ ЯЗЫКОВ Е,б. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ каждый раз, когда Р делает не е-такт. Р' допускает цепочку тогда и только тогда, когда ее допускает Р и А находится прн этом в заключительном состоянии. Детали доказательства оставляем в качестве упражнения. П В отличие от регулярных множеств КС-языки не образуют булеву алгебру множеств.
Теорема 2.27. Класс КС-языков не заикнут относипгельно пересечения и догголнения. Доказательство. Ег=-(а"Ь"с'!тг~ 1, 1- 1) и Ег= (а Ь"б" ~ г) 1, и~~1) — КС языки. Однако Е, 1! Е, = (а"Ь "с" ~ и) ! )— не КС-язык (см, пример 2.39). Таким образом, класс КС-языков не замкнут относительно перссечения. Отсюда можно также заключить, что класс КС-языков не замкнут относительно дополнения. В самом деле, в силу закона де Моргана любой класс языков, замкнутый относителыю объединения н дополнения, должен быть замкнут относительно пересечения.
Но по следствию из теоремы 2.25 класс КС.языков замкнут относительно объединения. П Существует много операций, относительно которых замкнут класс КС-языков. Некоторые из ннх приведены в упражнениях. В заключение этого раздела дадим несколько примеров применения свойств замкнутости к доказательству того, что некоторые множсства не являются КС-языками. Пример 2.41. Е=(вв!вЕ (а, Ь)".) ие КС-язык, Допустим, что это ие так.
Тогда по теореме 2.26 язык Е'. Е!)а Ь а+Ь+ = (а"Ь"аеЬ"!т, и !) контекстно-свободен. Но в упр. 2.8,3(д) утверждается, что Е* не КС-язык. Пример 2.42. Š— -(вв(в~(с, 1)") не КС-язык. Пусть Ь— такой гомоморфизм, чтой(с)=а и Ь(!) =Ь, Тогда Ь(Е).-=(вв) вЕ (а, Ь)+) не КС-язык (см. предыдущий пример). Так как класс КС-языков замкнут относительно гомоморфнзмов (следствие из теоремы 2.25), то Е не КС-язык. Пример 2.43. Алгол не является КС-языком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
