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

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

Конечный автомат может решать лишь вычислительные задачи, требующие фиксированного (конечного) объема памяти. Однако, в компиляторах существует множество задач, которые не могут быть решены при таком ограничении и поэтому приходится пользоваться моделью более сложного автомата [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}.

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

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

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

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

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

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

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

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

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

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

	0	1	
A	ВТОЛКНУТЬ(А), S1, СДВИГ	ВЫТОЛКНУТЬ, S2, СДВИГ	ОТВЕРГНУТЬ
	ВТОЛКНУТЬ(A), S1, СДВИГ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ

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

	0	1	
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 выталкивается из магазина. Работа такого автомата может быть представлена следующей таблицей:

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

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