Определение автомата с магазинной памятью (МП-автомата). Язык, допускаемый МП-автоматом. Расширенный МП-автомат

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

Автомат с магазинной памятью (МПА) – это семерка A=(N,T,V,d, n₀, v₀,F),

где N – множество состояний автомата;

T – конечный входной алфавит (множество допустимых символов);

V – специальный конечный алфавит магазинных символов автомата (обычно в него входят терминальные и нетерминальные символы грамматики), TÍV ;

d – функция переходов, отображающая множество N´(TÈ{e})´V на конечное множество подмножеств множества (N´V^*);

n₀ – начальное состояние автомата: n₀ÎN;

v₀ – начальный символ магазина: v₀ÎV;

K – множество конечных состояний автомата: KÍN, K¹Æ.

В отличие от КА МП-автомат имеет «стек» магазинных символов, который играет роль дополнительной, или внешней памяти.

Переход МПА из одного состояния в другое зависит не только от входного символа, но и от содержимого стека.

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

На каждом такте МПА

· считывает символ входной цепочки,

· из магазина удаляется верхний символ, соответствующий условию перехода, и заменяется цепочкой согласно правилу перехода

· первый символ цепочки становится вершиной стека.

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

Допускаются переходы (l–такты), при которых входной символ игнорируется, тогда он становится входным символом при следующем такте, но состояние и содержимое стека может измениться.

Автомат может проделывать l–такты, когда уже прочел входную цепочку; но, если магазин пуст, следующий такт невозможен.

Язык, определяемый МП-автоматом

МПА допускает цепочку символов w, если, получив эту цепочку на вход, он может перейти в одно из конечных состояний.

После окончания цепочки автомат может проделать некоторое количество –тактов.

Язык, определяемый МП-автоматом P – это множество всех цепочек символов, допускаемых этим автоматом: L(P). Два автомата P1 и P2 эквивалентны, если они определяют один и тот же язык: L(P1)=L(P2).

Говорят, что МПА допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из своих конечных состояний, а стек пуст.

Язык, заданный автоматом P, допускающим цепочки с опустошением стека, обозначается как L_l (P).

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

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

Варианты реализации алгоритма работы недетерминированного МПА.

Для произвольного МП-автомата всегда можно построить КС-грамматику, которая будет задавать язык, распознаваемый этим автоматом.

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

Недетерминированный МПА - устройство, реализующее перебор с возвратами, то есть неэффективный механизм распознавания языка.

Первый вариант

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

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

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

Если какая-то из последовательностей шагов приводит к заключительному состоянию, то цепочка считается принятой, а автомат заканчивает работу.

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

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

Если хотя бы одна из копий приводит в заключительное состояние, то цепочка распознана и работа всех остальных копий также завершается.

Если ни одна из копий не достигнет конечной конфигурации, алгоритм завершается с ошибкой и цепочка не принимается.

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

Количество копий алгоритма заранее неизвестно, их может быть много, в то время как количество одновременно выполняющихся процессов ограничено. Этим объясняется то, что большее распространение получил первый вариант алгоритма, который называется «разбором с возвратами».