Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 67
Текст из файла (страница 67)
7.8). Рис. 7 8. Дерево разбора в С' начинается деревом разбора в С и заканчивается многнии деревьями, соответствующими грамматикам С, Докажем, что описанная конструкция правильна в том смысле, что 0' порождает язык «(1,). Формально будет доказано следующее утверждение.
° Цепочка и принадлежит 1.(0) тогда и только тогда, когда и принадлежит «(Т.) (Достаточность) Пусть и принадлежит «(Т). Тогда существует цепочка х = аеаз.,.а„ в Т. и такие цепочки х, в «(а,) при 1 = 1, 2, ..., и, для которых зу = х,хз...х„. Тогда часть С; образованная продукциями из 0 с подстановками 8, вместо каждого а, порождает цепоч- ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ ху, которая выглядит, как х, но с э, вместо каждого а, т.е.
цепочку 5„5„н..5 . Эта часть порождения ю представлена верхним треугольником на рис. 7.8. Продукции каждой С, являются также продукциями С; поэтому порождение х, из 5„ есгь также порождение в С'. Деревья разбора для этих порождений представлены на рвс.7.8 нижними треугольниками. Поскольку крона этого дерева разбора в С' есть к~ел.л„= н, приходим к выводу, что и принадлежит ЕГС).
(Необходимость) Предположим, что и принадлежит Е(С). Утверждаем, что дерево разбора для зг должно выглядеть, как дерево на рис. 7.8. Причина в том, что переменане каждой из грамматик С и С„для а из Х попарно различны. Таким образом, верхушка дерева, начинающаяся переменной о, должна использовать только продукции С ао тех пор, пока не будет порожден некоторый символ ъ„, а под этим символом могут использоваться только продукции грамматики С,.
В результате, если и имеет дерево разбора Т, можно выделить цепочку а,а,... ан в Е(С) и цепочки х, в языках а(а,), для которых верно следующее. 1. и = х,хл ..х„. 2. Цепочка 5,5„н..Я„является кроной дерева, образованного из Т удалением некоторых поддеревьев (см. рис. 7.8).
Но цепочка х,хл..х„принадлежит з(Е), поскольку образована подстановкой цепочек х, вкесто каждого из а,. Таким образом, делаем вывод, что и принадлежит з(Е). П 7.3.2. Приложения теоремы о подстановке С использованием теоремы 7,23 можно обосновать несколько свойств замкнутости, хорошо знакомых нам по регулярным языкам. Перечислим их в следующей теореме. Теорема 7.24. Контекстно-свободные языки замкнуты относительно следующих операций.
1. Объединение. 2 Конкатенация. 3. Замыкание ( ) и транзитивное замыкание ('). 4. Гомоморфизм. Доказательство, Каждое утверждение требует лишь определения соответствующей аолстаиовки. Каждое из следующих доказательств использует подстановку контекстнооюбодных языков в другие, в результате чего по теореме 7.23 порождаются КС-языки. 1, Объединение. Пусть Е, и Ег — КС-языки, Тогда Е,0Е, является языком з(Е), где Š— язык (1, 2), аз — подстановка, определяемая как з(1) = Е, и з(2) =- Е,.
2. Конкатенация. Пусть Е~ и Еэ — КС-языки. Тогда Е~Еэ представляет собой язык з(Е), где Š— язык (12), а а — такая же подстановка, как и в п. 1. 83. СВОЙСТВА ЗАМКНУТОСТИ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 297 3. Замыкание и транэиаианое замыкание. Если Е, — КС-язык, Š— язык (1), а «вЂ” подстановка «(1) = Ен то Е, = «(Е).
Аналогично, если в качестве Е взять язык (1)', то Е; = «(Е). 4. Пусть Š— КС-язык над алфавитом Х, и и — гомоморфизм на Е. Пусты — подстановка, заменяющая каждый символ а из Х языком, состоящим из единственной цепочки Ь(а), т.е. «(а) = (!г(а) ) для всех а из Е. Тогда й(Е) = «(Е). 7.3.3. Обращение КС-языки замкнуты также относительно обращения. Для доказательства этого факта использовать теорему о подстановках нельзя, но существует простая конструкция на основе грамматик. Теорема 7.25.
Если Š— КС-язык, то и Š— КС-язык. Доказательство, Пусть Е, — Е(О) для некоторой КС-грамматики О = (1; Т, Р, 5). Построим сж = (1; Т, Р», В), где продукции Р представляют собой "обращения" продукций из Р. Таким образом, если А -» а — продукция С, то А -ь ໠— продукция б~. С помощью индукции по длине порождений в с и С нетрудно показать, что Е(6 ) =Е».
По сути, все выводимые в Еж цепочки являются обращениями цепочек, выводимых в с, и наоборот. Формальное доказательство оставляется в качестве упражнения. П 7.3.4. Пересечение с регулярным языком КС-языки не замкнуты по пересечению. Это доказывает следующий простой пример. Пример 7.2б.
В примере 7.19 было выяснено, что язык Е = (О"! "2" ~ > 1) не является контекстно-свободным. Однако следующие два — контекстно-свободные. Е = (О"! "2' ~ л > 1, ! > ! ) Е = (О'1 "2" ( л > 1, 1 > 1) Первый из них порождается следующей грамматикой. А — ч ОА! )01  — з2В)2 В этой грамматике А порождает все цепочки вида 0" 1", а  — все последовательности двоек. Аналогична и грамматика для второго языка. А — +ОА(0 В -+ !В2 ( 12 Здесь А порождает все последовательности нулей, а  — цепочки вида 1 "2". ГЛАВА 7.
СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 298 Однако 7. = 7.т П 7.з. Чтобы в этом убедиться, заметим, что Ег требует равных количеств нулей и единиц в цепочках, тогда как Ег — равных количеств единиц и двоек. По- этому цепочка из пересечения этих языков должна иметь поровну каждого из символов д следовательно, принадлежать |.
Если бы КС-языки были замкнуты по пересечению, то мы могли бы доказать ложное утверждение о том, что А — контекстно-свободный язык. Полученное противоречие позволяет заключить, что КС-языки не замкнуты по пересечению. ЕЗ Вместе с тем, есть более слабое утверждение о пересечении.
КС-языки замкнуты относительно операции "пересечение с регулярным языком". Формальное утверждение и его доказательство представлены в следующей теореме. Теорема 7.27. Если 7. — КС-язык, а и — регулярный язык, то 7. Й й является КС- языком. Доказательство. Нам понадобится представление КС-языков с помощью МП- мтоматов, а также конечноавтоматное представление регулярных языков. Данное дохматеяьство обобщает доказательство теоремы 4.8, где для получения пересечения регулярных языков "параллельно запускались" два конечных автомата. Здесь конечннй автомат запускается параллельно с МП-автоматом, и в результате получается еще один МП-автомат (рис. 7.9). Вход Допустить/отеергнтпь Рис.
7.9. для создания нового ЛзП-автомата конечный автомат и ИП-автомат запускаются параллельно Формально, пусть ВЗ. чЗОЙСТВА ЗАМКНУТОСТИ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 299 Р = (Я,, Х, Г, 6,, д!ь си Ре)— МП-автомат, допускающий Е по заключительному состоянию, и пусть '4 (0А ~ БА ЧА Р«) ДКА для Я. Построим МП-автомат где 6((д, р), а. Х) определяется как множество всех пар ((г, «), у), где « = 6 «(Р, а) и пара (г, у) принадлежит Бр(д, А, Х). Таким образом, для каждого перехода МП-автомата Р мы можем совершить такой же переход в МП-автомате Р; дополнительно отслеживая состояние ДКА А во втором компоненте состояния Р'.
Отметим, что а может быть символом из Т. или я. В первом случае 6 «(Р, а) = 6«(р, а), но если а = «, то Б «(Р, а) = р, т.е. А не меняет состояние, когда Р со- вершает к-переход. С помошью простой индукции по числу переходов, совершаемых МП-автоматами, нетрудно доказать, что (с7!ь и, У«) (- (!), я, у) тогда и только тогда, когда ((др, су„), и, У,) (- л Р' ((Ч р) ж у), где р= 6з(р, и). Эти индукции оставляются в качестве упражнения. Но (!1, р) является допускающим состоянием Р' тогда и только тогда, когда д — допускающее состояние Р и Р— лопускаюшее состояние А.
Отсюда заключаем, что Р'допускает и тогда и только тогда, когда его допускают Р и А вместе, т.е. и принадлежитЕ () 6. П Пример 7.28. На рис. 6.6 был определен МП-автомат Р; допускающий по заключительному состоянию множество цепочек, которые состоят из ! и е.
Такие цепочки представляют минимальные нарушения правил, определяюших, в каком порядке слова ЕЕ и е1ве могут встречаться в С-программах. Назовем этот язык Е. МП-автомат Р был определен так: Рк=((Р, !),г), (!; е), (с Х«), 4:,Р,Хо, (г)) где Б!: состоит из следующих правил. 1. 6!.(Р, е, Хо) = ((4!, 7Х«) ). 2. 6!(д, !', х) = ((д, Е2)). 3. 6«(Ф е, 2) = ((!7, е)). 4. 6«(!7, е, Х«) = ((г, к)).
Теперь определим конечный автомат .4 = ((«, !), (Е е), Бж «, («, !)), допускающий цепочки языка! е, т.е. все цепочки, в которых символы е следуют за Е На- зовем этот язык 1«, Функция переходов 6«определяется следуюшими правилами; ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОВОДНЫХ ЯЗЫКОВ ЗОО а) б«(«, ~)=«; б) б«(«, е) =б в) б«(б е) = а Строго говоря, А не является ДКА, как предполагается в теореме 7.27, поскольку в нем отсутствует дьявольское состояние лля случая, когда вход ~' получен в состоянии а Однако такая же конструкция работает даже для НКА, так как МП-автомат, который строится, колет быть недетерминированным. В данном же случае МП-автомат на самом деле детермянирован, хотя и "умирает'* на некоторых входных последовательностях.
Построим следующий МП-автомат. Р = ((Р, 4, г) х («, г), (ч', е), («., Хо), б, (Р, «), Х„(г) х («, 1) ) Переходы д перечислены ниже и проиндексированы номерами правил для МП-автомата Р(числа от! до 4) и правил для ДКА А (буквы а, б, в). Если МП-автомат Р совершает «- переход, правило для А не используется. Отметим, что правила для автомата Р строятся "ленивым" способом: правила для состояния строятся только тогда, когда обнаружено, что оно достигается из начального состояния Р. 1 б((Р, «), г, Х.) = (((7, а), ~Хо)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
