XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 98
Текст из файла (страница 98)
Обратим внимание на различие структур „накачиваемых" цепочек в регулярных и контекстно-свободных языках. Лемма о разрастании для регулярных языков утверждает, что любая достаточно длиннэл цепочка регулярного языка представимакак соединениетрехподцепочек, изкоторых средняя подцепочка ограничена сверху по длине и не пуста, ее можно „накачивать", повторял любое число рэз, в том числе В.З. Лемма о рвврастввии длв КС-языков 623 и ни разу, т.е.
можно выбросить вообще, и такая „накачка" не выводит за пределы данного языка (рис. 8.26). Рис. 8.28 Лемма о разрастании для КС-языков утверждает в аналогичной ситуации, что цепочка языка представима как соединение пяти подцепочек, причем если рассмотреть три средние подцепочки, то „накачиваютсяв крал — первая и третья из них, а самая середина не меняетсл (рис. 8.27). Рис. 8.27 Обратим внимание на то, что ограничение сверху длины подцепочки хну константой й, вытекающее из леммы о разрастании, очень важно и, не используя его, вообще говоря, нельзя доказать, что данный язык не является контекстно-свободным.
Рассмотрим в этой связи такой пример. Пример 8.12. Пусть язык Ь определе~ как множество всех цепочек в алфавите (а, Ь) вида а"Ьо'а"Ьв', и ) О. Докажем, что он не является контекстно-свободным. Предполагая, что Ь вЂ” КС-язык, получим, что для достаточно больших и и ш цепочка а"Ь"'аоЬ'в допускает представление в виде изчоуе. Выберем числа п и еп так, что они больше, чем определенная леммой о разрастании константа Й для языка Ь. Анализируем варианты „размещения" подцепочки хшу в цепочке а" ЬоаоЬ'в: очевидно, что „накачка" невозможна, если б24 8.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ цепочки х и у обе целиком находятся в „зоне" какого-то одного символа, а или Ь; если же, скажем, х = аЯЬ' при р, я ~ О, т.е. цепочка х находится „на стыке зон" символов а и Ь, то при „накачке" возникнет более чем одно вхождение подцепочки Ьа в цепочку языка Ь, что противоречит определению этого языка; если же х = Ьга' при р, е ф О, то при „накачке" возникнет более двух вхождений подцепочки аЬ, что также невозможно.
Аналогично анализируется размещение цепочки р „на стыках зон". В силу того что и, т > й, а ~хшу~ < й, никакие другие варианты расположения подцепочки хатор невозможны. Если ограничение на длину этой подцепочки опустить, то окажется возможным такое ее вхождение в цепочку а"'6"а""Ь", что х = а', ш = агЬЯ'аЯ и р = а' для некоторых положительных з, р, д, г. Тогда при я = г (чего априори нельзя отвергать, так как условия леммы о разрастании не требуют, чтобы длины цепочек х и р бь|ли обязательно различными) „накачка" цепочек х и р дала бы „синхронное" увеличение числа символов а при неизменном числе символов Ь, что не вывело бы нас за пределы языка Ь.
Таким образом, нам тогда не удалось бы доказать, что определяемое леммой о разрастании представление цепочки а Ь"а~Ь" не может иметь места. Рассмотрим еще один пример, важный для понимания леммы о разрастании и ее применений. Пример 8.13. Зададим язык Ь' = 1а"Ь"сг: п,р > О и р > и) . Здесь при размещении „накачиваемых" цепочек в „зоне" символов с „накачка" не выводит за пределы языка Ь' (так как в его цепочках число символов с может на сколько угодно превьппать число символов а и Ь). Тем не менее и в этом случае условие леммы о разрастании не выполняется.
Действительно, для достаточно большого и возьмем цепочку а" Ь" с" е Ь' (т.е. цепочку языка Ь' при и = р). Если в представлении такой цепочки в виде а"6" сЯ = ихшуе (согласно лемме о 625 В.4. Мвгвэиллые автоматы разрастании) цепочка хюу = с' при О < 1 < п (т.е. „накачиваемые" цепочки располагаются целиком в „зоне" символов с), то )~ф ~ П т.е. число символов с окажется меньше, чем число символов а и Ь. Таким образом, несмотря на то что „накачка" цепочек х,у в данном случае возможна, нельзя их выбросить, оставаясь в пределах языка. Невозможность других вариантов расцоложения надцепочки хюу в цепочке языка Ь' доказывается точно так же, как и в предыдущих примерах. ф Итак, нужно помнить, что выполнение условий леммы о разрастании предполагает и возможность выбрасывания „накачиваемьпсл цепочек — все цепочки х„= их"юуво из условия леммы при и ) О должны оставаться в языке т'., и если условие леммы выполняется при всех положительных и, но не выполняется при п = О, то этого достаточно для признания того, что цепочка х = ихюуо Е Ь не удовлетворяет условию леммы о разрастании.
Аналогичная ситуация имеет место, конечно, и при использовании леммы о рвэрзстнии для регулярных языков. 8.4. Магазинные автоматы Автоматы с магазинной памятью, или магазинные автпоматпы (сокращенно — МП-автпоматпы), образуют класс распознающих моделей для КС-языков точно так же, как конечные авшоматпы являются распознающими моделями в классе регулярных языков. Понятие МП-автомата является частным случаем общего интуитивного понятия автпомапта, которое мы ввели в Т.б. Как и всякий автомат, МП-автомат — это устройство, имеющее блок управления, входную лентпу, головку и блок внушренней памяши в виде магазина МП-автпоматпа (или стека).
Блок управления в каждый момент времени находится в одном из конечного множества Я сосшояний. 626 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Входная лента предполагается „полубесконечной", т.е. она имеет начало (елевый край"), но не имеет конца. Лента разделена на ячейки, пронумерованные от крайней левой ячейки натуральными числами, начиная с единицы; в каждой ячейке может быть записан символ алфавита У, называемого входным алфавитом МП-авпгомапга. В каждый момент вреВходная лента мени читающая головка обозревает (или читает) некоторую ячейку входной ленты.
г сно Если в втой ячейке записан Блок Я некоторый входной символ,т.е. символ входного алфавита, то управления его называют обозреваемым (в данный момент) входным символом (рис. 8.28). Предполагается, что если на ленте записана некоторая непустая цепочка х = х(1)х(2)...х(й) во входном алфавите, то ее символы последовательно записаны в ячейках от первой до й-й, без пропусков, так, что символ х(г) записан в г-й ячейке (рис.
8.29). Рие. 8.29 МП-автомат может читать цепочку х, продвигая головку только в одном направлении, слева направо, по шагам, причем за каждый шаг головка переходит от обозреваемой ячейки к следующей. Если в какой-то момент времени обозревается символ х(г), 1 < г < й, записанной на ленте цепочки х, то ненрочинганноб часнгыо входной иенонни х будет подцепочка х(г + 1)...х(й).
В частности, при г = й непрочитанная часть совпадает с пустой цепочкой, и тогда говорят, что цепочка х полностью прочитана МП-автоматом (рис. 8.30). 627 8.4. Магазинные автоматы Рис. 8.30 Магазин МП-автомата устроен и работает следующим образом. Как и входная лента, магазин является полубесконечным и разделенным на пронумерованные ячейки, в каждой из которых может быть записан символ алфавита Г, называемого магазинным алЯаеитпом МП-аептоматпа Входной и магазинный алфавиты МП-автомата могут пересекаться и даже совпадать друг с другом. Символы алфавита Г называют маеаэинными символами.
Первую ячейку магазина называют его верхней ячейкой (иногда просто верхом маеазина'). Символ, в данный момент записанный в верхней ячейке магазина, называют верхним симео,лом маеазина. Единственная операция, которую МП-автомат может реализовать с магазином, состоит в следующем: верхний символ Я магазина заменяется некоторой цепочкой у магазинных символов. а При зтом если цепочка у непустая, то она за- 7(тп) писывается в первых тп ячейках, где тп = Ц (длине цепочки у), так, что ее первый символ Р .881 становится верхним символом магазина.
Если до замены Я цепочкой у под верхней ячейкой"" (т.е. в ячейках, начиная со второй) была записана какая-то цепочка ст, то после замены она сдвигается „в глубь" магдзина и оказывается записанной уже в ячейках, начинал с (та+ 1)-й (рис. 8.31). Если же верхний символ Я заменяется пустой цепочкой А, то после такой замены верхним символом магазина становится "Таким образом, в неформальном описании МП-автомата лента читаетсл „слева направо", а магазин — „сверху вниз". "Полагают, что, как и символы цепочек на входной ленте, символы цепочек, записанных в магазин, располагаютсл в последовательных лчейках „сверху вниз" без пропусков лчеек. 628 8.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ первый символ цепочки а (записанной под верхней ячейкой магазина), т.е. цепочка а „поднимается" на одну ячейку. В случае, когда а — пустая цепочка, замена верхнего символа магазина пустой цепочкой у приводит к опустошению магазина (ни в одной из ячеек магазина не записан магазинный символ). Заметим, что, по определению, с пустым магазином МП-автомат не может производить никаких операций. Описанная вьппе операция с магазином составляет основу поведения МП-автомата, его, образно говоря, „динамику". Эта „динамика" определяется саспземоб команд МП- авпзоматпа, которая, аналогично сисшеме команд конечного автвоматаа, определяется как конечное множество 6 команд, каждая из Которых записывается в виде (8.8) оаЯ~ту, где о и т — состояния из множества ф а — входной символ или пустая цепочка; Я вЂ” магазинный символ; 7 — цепочка магазинных символов (может быть и пустая).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
