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

Отдельные вопросы теории вычислительных процессов

Конечный автомат может решать лишь вычислительные задачи, требующие фиксированного (конечного) объема памяти. Однако, в компиляторах существует множество задач, которые не могут быть решены при таком ограничении и поэтому приходится пользоваться моделью более сложного автомата [3]. Например, задача обработки скобок арифметических выражений не может быть решена с помощью конечного автомата, потому что арифметическое выражение может начинаться с любого количества левых скобок и компилятор должен проверять соответствие их числу правых скобок. Заранее число левых и правых скобок не известно.

Автомат с магазинной памятью имеет расширенную память по сравнению с конечным автоматом за счет возможности дополнительного хранения информации в магазине (стеке). Часто в программировании стек и магазин считаются синонимами, однако, стек имеет более широкий смысл в теории автоматов. Стек в русском языке имеет аналогию со стопкой, например, книг.

Основная особенность магазинной памяти с точки зрения работы с ней состоит в том, что символы могут помещаться в магазин и удаляться из него по одному, причем удаляемый символ - это всегда тот, который был помещен в магазин последним. Когда символ помещается в магазин, говорят, что он «вталкивается» в магазин, а когда удаляется - «выталкивается». Говорят, что только что поступившая информация находится наверху магазина. Считается, что на дне магазина всегда находится символ Ñ - маркер дна, он никогда не вталкивается и не выталкивается из магазина. Если в магазине находится только символ Ñ, то говорят, что магазин пуст. Символы в магазине находятся в том порядке, в котором они поступали в магазин. Магазин можно изображать в виде цепочки одним из следующих способов:

1. C A B Ñ 2. Ñ B A C

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

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

· состояние;

· верхний символ магазина;

· текущий входной символ.

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

· над магазином;

· над состоянием;

· над входом.

Возможные операции:

1. Операции над магазином:

· втолкнуть в магазин определенный магазинный символ;

· вытолкнуть верхний символ магазина;

· оставить магазин без изменения.

2. Операции над состояниями:

· перейти в заданное новое состояние;

· остаться в прежнем состоянии.

3. Операции над входом:

· перейти к следующему входному символу и сделать его текущим

входным символом;

· оставить данный входной символ текущим, то есть держать его

до следующего шага.

Определение. Автомат с магазинной памятью есть формальная система, задаваемая следующими пятью формальными объектами:

1) конечным множеством входных символов, в которое входит и

концевой маркер ¿ (маркер конца цепочки);

2) конечным множеством магазинных символов, включающем

маркер дна;

3) конечным множеством состояний, включая начальное состояние;

4) управляющим устройством, которое каждой комбинации

(входной символ, магазинный символ, состояние) ставит в

соответствие выход или переход. Переход в отличие от выхода

заключается в выполнении операции над магазином, состоянием и

входом. Операции, которые запрашивали бы входной символ после

концевого маркера или выталкивали из магазина или вталкивали в

магазин маркер дна исключаются;

5) начальным содержимым магазина является маркер дна, за которым следует (возможно, пустая) цепочка других магазинных символов.

Определение. Автомат с магазинной памятью называется распознавателем, если у него 2 выхода: ДОПУСТИТЬ и ОТВЕРГНУТЬ.

Говорят, что цепочка символов входного алфавита допускается распознавателем, если под действием этой цепочки автомат, начавший работу в своем начальном состоянии и с начальным содержимым магазина, делает ряд переходов, приводящих к выходу ДОПУСТИТЬ. В противном случае цепочка отвергается.

При описании переходов автомата с магазинной памятью будем обозначать действия автомата словами:

· ВЫТОЛКНУТЬ,

· ВТОЛКНУТЬ (А),

· СОСТОЯНИЕ (Si),

· СДВИГ,

· ДЕРЖАТЬ.

Здесь А - магазинный символ, операция СОСТОЯНИЕ (Si ) означает, что следующим состоянием автомата становится состояние Si, операция СДВИГ означает, что текущим входным символом становится следующий входной символ. В некоторых реализациях это может означать сдвиг указателя на входе. Операция ДЕРЖАТЬ означает, что текущий входной символ следует держать до следующего шага.

Пример. Построить автомат с магазинной памятью, для распознавания

скобок.

Решение. Предлагается следующий принцип работы такого распознавателя. Каждый раз, когда встречается левая скобка, в магазин вталкивается символ А, а когда встречается правая - символ А выталкивается. Цепочка отвергается, если на входе остаются правые скобки, а магазин пуст (лишние правые скобки) или, если цепочка прочитана до конца, а в магазине остаются символы А (лишние левые скобки). Такой автомат с магазинной памятью определяется следующими объектами:

1) входным множеством { ( , ), ¿ };

2) множеством магазинных символов { А, Ñ};

3) множеством состояний {Si }, где i = 1..n, S - начальное

состояние, n - число внутренних состояний автомата;

4) переходами:

(, A, S = ВТОЛКНУТЬ (А), СОСТОЯНИЕ (S), СДВИГ.

(, Ñ, S = ВТОЛКНУТЬ (А), СОСТОЯНИЕ (S), СДВИГ.

), A, S = ВЫТОЛКНУТЬ, СОСТОЯНИЕ (S), СДВИГ.

), Ñ, S = ОТВЕРГНУТЬ (лишние правые скобки).

¿, A, S = ОТВЕРГНУТЬ (лишние левые скобки).

¿, Ñ, S = ДОПУСТИТЬ.

5) начальным содержимым магазина {Ñ}.

Пусть на вход автомата подается цепочка ( ( ) ( ) ), тогда работа такого автомата может быть представлена следующей таблицей переходов:

Состояние магазина	Входные символы
(	)	¿
A	ВТОЛКНУТЬ(А) СДВИГ	ВЫТОЛКНУТЬ СДВИГ	ОТВЕРГНУТЬ
Ñ	ВТОЛКНУТЬ(А) СДВИГ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

Пример. Построить автомат, распознающий правильность построения цепочек языка {0ⁿ 1ⁿ, n > 0}.

Решение.Предлагается следующий принцип работы автомата:

n начальный отрезок цепочки, состоящий из нулей вталкивается в магазин;

n каждый раз, когда встречается единица на входе, один нуль выталкивается из магазина;

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

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

Для построения автомата введем две фазы процесса обработки:

· первая фаза - « ВТАЛКИВАНИЕ»;

· вторая фаза - « ВЫТАЛКИВАНИЕ ».

Чтобы автомат «помнил», в какой фазе он находится, введем два внутренних состояния S1 и S2, соответствующие этим фазам. Построим управляющую таблицу.

Состояние S1(обработка нулей):

			¿
A	ВТОЛКНУТЬ(А), S1, СДВИГ	ВЫТОЛКНУТЬ, S2, СДВИГ	ОТВЕРГНУТЬ
Ñ	ВТОЛКНУТЬ(A), S1, СДВИГ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ

Состояние S2 (обработка единиц):

			¿
A	ОТВЕРГНУТЬ	ВЫТОЛКНУТЬ, S2, СДВИГ	ОТВЕРГНУТЬ
Ñ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

Рассмотренный автомат характеризовался следующими объектами:

1) входным множеством {0,1, ¿ };

2) множеством магазинных символов {А, Ñ}.

3) множеством состояний {S1, S2}, где S1 - начальное состояние;

4) таблицами переходов (см. выше);

5) начальным содержимым магазина {Ñ}.

Рассмотрим другой подход, применимый в решении поставленной задачи, который позволит обойтись лишь одним состоянием S вместо двух примененных. Для этого введем в рассмотрение операцию ЗАМЕНИТЬ (A, B, C). Она эквивалентна последовательности операций:

· ВЫТОЛКНУТЬ,

· ВТОЛКНУТЬ (А),

· ВТОЛКНУТЬ (B),

· ВТОЛКНУТЬ (C).

Если эта операция применяется к магазину {Ñ X Y Z} , то новый магазин будет выглядеть следующим образом: { Ñ X Y A B C}.

Вернемся к задаче распознавания множества {0ⁿ 1ⁿ, n > 0}. Построим другой автомат, в котором будет достаточно одного конечного состояния. Предлагается следующий принцип работы. Символ А вталкивается в магазин при каждом появлении на входе нуля и выталкивается при каждом появлении на входе единицы. Для отличия фаз вталкивания и выталкивания применим новую стратегию. Во время фазы вталкивания в верхней ячейке магазина хранится новый магазинный символ X. Единственное его назначение - напоминать управляющему устройству, что автомат находится в фазе вталкивания. Когда впервые на входе появится единица, X выталкивается из магазина. Работа такого автомата может быть представлена следующей таблицей:

			¿
X	ЗАМЕНИТЬ (А,X), СДВИГ	ВЫТОЛКНУТЬ, ДЕРЖАТЬ	ОТВЕРГНУТЬ
А	ОТВЕРГНУТЬ	ВЫТОЛКНУТЬ СДВИГ	ОТВЕРГНУТЬ
Ñ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

( Начальное состояние магазина {Ñ X}.