2.5. Автомат с магазинной памятью и языки типа 2

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

(магазин), которая может двигаться „вверх" и „вниз“. Если в результате движения ленты памяти символ помещается „над" ее читающей головкой, то этот символ теряется. По аналогии с движением тарелок в стопке посуды в кафетерии операции движения символов „вверх" и „вниз" иногда называют «выталкивание» и «заталкивание». На языке исследования операций лента памяти работает как очередь, организованная по принципу „последним пришел — первым вышел". Эта лента предоставляет ограниченный доступ к бесконечной памяти, так как, если символ от последнего, записанного на ленте, должен быть прочитан, промежуточных символов должны сначала быть стерты.

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

допускающем следующую интуитивную интерпретацию:

Если в состоянии символ находится наверху магазина и считан входной символ а, то надо затолкнуть магазин и написать на нем символ

Для алфавита магазина необходим специальный „символ выталкивания" Команда „записать Ь°“ интерпретируется как „вытолкнуть магазин".

Язык воспринимается МП-автоматом тогда и только тогда, когда это язык типа 2.

Это чрезвычайно важный результат для теории вычислений, поскольку наиболее традиционные языки программирования (за редким исключением) являются языками типа 2. Фактически большинство трансляторов сознательно конструировались как МП-автоматы. Техника программирования для управления динамической памятью в МП-автоматах очень хорошо развита. Интересующемуся читателю рекомендуем работу Гриса (1971).

Искусственный интеллект включает в себя ряд задач, которые, хотя на первый взгляд и не имеют отношения к лингвистике, допускают формулировку в виде задач вычисления функций, область определения которых — язык типа 2. Удивительно, как много задач распознавания и обработки изображений можно трактовать таким образом. (Примеры приводятся в части II этой книги.) Как только проблема сформулирована в терминах распознавания языка типа 2, мы получаем возможность пользоваться обширными знаниями, накопленными вычислительными науками для работы с такими языками. Поэтому часто стоит проанализировать соотношение между

исследуемой задачей и языками типа 2, чтобы выбрать структуру нужной программы.

Существует интересная взаимосвязь между типом 2 и более ограниченным типом 3. Каждая продукция грамматики типа 2 развертывает переменную в цепочку. Если продукции грамматики таковы, что

для некоторой переменной А (т. е. если цепочка, содержащая А, выводима из А), то грамматику называют грамматикой с самовставлением. Если грамматика типа 2 не является грамматикой с самовставлением, то найдется грамматика типа 3, порождающая тот же самый язык. В следующем разделе мы опишем очень простую модель автомата, воспринимающего языки типа 3; эта модель непосредственно определяет структуру программы. Встречаются случаи, когда наиболее очевидная грамматика относится к типу 2 и при ближайшем рассмотрении выясняется, что она без самовставления. В таких случаях обычно стоит сконструировать грамматику типа 3 (возможно, интуитивно менее ясную), которая порождает тот же язык, и использовать ее как руководство при программировании.