Магазинные автоматы

625 В.4. Магазинные автоматы разрастании) цепочка хюу = с' при О < 1 < п (т.е. „накачиваемые" цепочки располагаются целиком в „зоне" символов с), то )~ф ~ П т.е. число символов с окажется меньше, чем число символов а и Ь. Таким образом, несмотря на то что „накачка" цепочек х,у в данном случае возможна, нельзя их выбросить, оставаясь в пределах языка. Невозможность других вариантов расцоложения надцепочки хюу в цепочке языка Ь' доказывается точно так же, как и в предыдущих примерах. ф Итак, нужно помнить, что выполнение условий леммы о разрастании предполагает и возможность выбрасывания „накачиваемьпсл цепочек — все цепочки х„= их"юуво из условия леммы при и ) О должны оставаться в языке т'., и если условие леммы выполняется при всех положительных и, но не выполняется при п = О, то этого достаточно для признания того, что цепочка х = ихюуо Е Ь не удовлетворяет условию леммы о разрастании. Аналогичная ситуация имеет место, конечно, и при использовании леммы о рвэрзстнии для регулярных языков.

8.4. Магазинные автоматы Автоматы с магазинной памятью, или магазинные автпоматпы (сокращенно — МП-автпоматпы), образуют класс распознающих моделей для КС-языков точно так же, как конечные авшоматпы являются распознающими моделями в классе регулярных языков.

Понятие МП-автомата является частным случаем общего интуитивного понятия автпомапта, которое мы ввели в Т.б. Как и всякий автомат, МП-автомат — это устройство, имеющее блок управления, входную лентпу, головку и блок внушренней памяши в виде магазина МП-автпоматпа (или стека). Блок управления в каждый момент времени находится в одном из конечного множества Я сосшояний. 626 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Входная лента предполагается „полубесконечной", т.е. она имеет начало (елевый край"), но не имеет конца.

Лента разделена на ячейки, пронумерованные от крайней левой ячейки натуральными числами, начиная с единицы; в каждой ячейке может быть записан символ алфавита У, называемого входным алфавитом МП-авпгомапга. В каждый момент вреВходная лента мени читающая головка обозревает (или читает) некоторую ячейку входной ленты. г сно Если в втой ячейке записан Блок Я некоторый входной символ,т.е. символ входного алфавита, то управления его называют обозреваемым (в данный момент) входным символом (рис.

8.28). Предполагается, что если на ленте записана некоторая непустая цепочка х = х(1)х(2)...х(й) во входном алфавите, то ее символы последовательно записаны в ячейках от первой до й-й, без пропусков, так, что символ х(г) записан в г-й ячейке (рис. 8.29). Рие. 8.29 МП-автомат может читать цепочку х, продвигая головку только в одном направлении, слева направо, по шагам, причем за каждый шаг головка переходит от обозреваемой ячейки к следующей. Если в какой-то момент времени обозревается символ х(г), 1 < г < й, записанной на ленте цепочки х, то ненрочинганноб часнгью входной иенонни х будет подцепочка х(г + 1)...х(й).

В частности, при г = й непрочитанная часть совпадает с пустой цепочкой, и тогда говорят, что цепочка х полностью прочитана МП-автоматом (рис. 8.30). 627 8.4.Магазинные автоматы Рис. 8.30 Магазин МП-автомата устроен и работает следующим образом. Как и входная лента, магазин является полубесконечным и разделенным на пронумерованные ячейки, в каждой иэ которых может быть записан символ алфавита Г, называемого магазинным алфавипзом МП-автпоматпа. Входной и магазинный алфавиты МП-автомата могут пересекаться и даже совпадать друг с другом.

Символы алфавита Г называют магазинными символами. Первую ячейку магазина называют его верхней ячейной (иногда просто верхом магазина' ). Символ, в данный момент записанный в верхней ячейке магазина, называют верхним символом магазина. Единственная операция, которую МП-автомат может реализовать с магазином, состоит в следующем: верхний символ Я магазина заменяется некоторой цепочкой у магазинных символов. а При этом если цепочка у непустая, то она за- т(тв) писывается в первых гп ячейках, где уп = Ц (длине цепочки у), так, что ее первый символ Рис.

8.31 становится верхним символом магазина. Если до замены Я цепочкой у под верхней ячейкой" (т.е. в ячейках, начиная со второй) была записана какая-то цепочка а, то после замены она сдвигается вв глубь" магазина и оказывается записанной уже в ячейках, начиная с (пз+ 1)-й (рис. 8.31). Если же верхний символ Я заменяется пустой цепочкой Л, то после такой замены верхним символом магазина становится 'Таким образом, в неформальном описании МП-автомата лента читаетсл „слева направо", а магазин — „сверху вниз". "Полагают, что, как и символы цепочек на входной ленте, символы цепочек, записанных в магазин, располагаютсл в последовательных лчейках „сверху вниз" без пропусков лчеек.

628 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ первый символ цепочки а (записанной под верхней ячейкой магазина), т.е. цепочка а „поднимается" на одну ячейку. В случае, когда а — пустая цепочка, замена верхнего символа магазина пустой цепочкой у приводит к опустошению магазина (ни в одной из ячеек магазина не записан магазинный символ). Заметим, что, по определению, с пустым магазином МП-автомат не может производить никаких операций.

Описанная вьппе операция с магазином составляет основу поведения МП-автомата, его, образно говоря, „динамику". Эта „динамика" определяется саспземоб команд МП- авпзоматпа, которая, аналогично сисшеме команд конечного автвоматаа, определяется как конечное множество 6 команд, каждая из Которых записывается в виде (8.8) оаЯ~ту, где о и т — состояния из множества ф а — входной символ или пустая цепочка; Я вЂ” магазинный символ; 7 — цепочка магазинных символов (может быть и пустая). Если в системе команд 6 МП-автомата М есть команда (8'.8), то М может в данный момент времени выполнить зту команду, если и только если в данный момент времени его блок управления находится в состоянии о, головка обозревает входной символ а (при условии, что а ф Л), а верхним символом магазина является символ Я.

Выполнение команды (8.8) состоит в замене верхнего символа магазина цепочкой у (как зто описано вьппе), переходе блока управления в состояние т (которое может и совпадать с состоянием д) и в продвижении головки на одну ячейку вправо (если а в команде (8.8) не есть пустая цепочка А) (рис. 8.32). Если же в команде (8.8) а = А, то такую команду МП- автомат может выполнить всякий рэз, когда его блок управления окажется в состоянии о, а верхним символом магазина будет символ Я. В этом случае выполнение команды никак не 629 В.4. Мегееннные автоматы Входная ленте Входная ленте Рнс. 8.32 зависит от содержимого входной ленты, а после ее выполнения головка остается на прежнем месте. Рассмотренную вьппе процедуру выполнения команды вида (8.8) называют шагом (или тпактпом) работпы МП-авптоматпа (ври а = Л такт работы называют Л-тттактпом).

Предположим теперь, что в множестве состояний Я блока управления МП-автомата М с системой команд 6 фиксировано некоторое начальное состполние де и подмножество заключитпельных состполний Р. Пусть в какой-то начальный момент времени блок управле ния МП-автомата М находится в начальном состоянии де, на ленте записана непустел цепочка х, головка обозревает первую ячейку ленты и, следовательно, первый символ цепочки х является обозреваемым, а в магазине записан только один специальный символ Яе, называемый начальным символом магазина.

Тогда, если МП-автомат М, выполняя некоторую последовательность команд иэ б, прочитывает полностью цепочку х, в результате чего блок управления переходит в некоторое заключительное состояние ду Е г', говорят, что МП-автомат М допускает (распознает, воспринимает) цепочку/х, которую называют допустпимой цепочкой МП-автпоматпа. Множа.

ство всех допустимых цепочек МП-автомата М образует язык, допускаемый этим МП-автпоматпом. 63Р 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Далее мы докажем, что язык любого МП-автомата является КС-языком и, наоборот, любой КС-язык есть язык некоторого МП-автомата. В этом смысле мы и говорим об МП-автоматах как о „распознавателях" КС-языков: всякий МП-автомат допускает те и только те цепочки входных символов, которые порождаютсл некоторой КС-гряммашикой. Но чтобы доказывать какие-либо утверждения об МП-автоматах, нужно сначала дать строгое математическое определение этого понятия, не апеллируя уже к наглядным, но не определенным формально идеям ленты, магазина, головки и т.п. Формализация изложенного вьппе описания проводится во многом аналогично построению определения порождающей грамматики.

Определение 8.7. МП-автомат задается упорядоченной семеркой М = Я~ К Г Чо Р ~о, б), где Я вЂ” конечное множество состояний; У вЂ” алфавит, называемый входным алфавитом; à — алфавит, называемый магазинным алфавитом; де Е Я вЂ” начальное состояние; г' С Я— подмножество заключительных состояний; Яз е à — начальный магазинный символ; б — система команд, определенная как конечное множество команд, каждая иэ которых записывается в виде (8.8): яоЯ -~ г7, где знак „-~" (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов); д, г Е ф а Е У 0 (Ц; Я Е Г; 7 Е Г'.

Замечание 8.8. Нелишне обратить внимание на то, что упоминание о ленте и магазине в приведенном вьппе формальном определении совершенно необязательно. Формально для определения МП-автомата достаточно задать два алфавита, конечное множество состояний, выделив в нем начальное состояние и подмножество заключительных состояний, а также 631 8.4.